用100道题拿下你的算法面试（数组篇-12）：最大环形子数组和

张

张建站

2026/5/16 1:07:27

10分钟阅读

一、面试问题给定一个环形数组 arr[]求出任意非空子数组的最大和。环形数组允许从数组末尾绕回到数组开头。注意子数组可以跨越末尾并从开头继续形成一个环形片段。示例 1输入arr [] [8, -8, 9, -9, 10, -11, 12]输出22解释环形子数组 [12, 8, -8, 9, -9, 10] 的和最大为 22。示例 2输入arr [] [4, -1, -2, 3]输出7解释环形子数组 [3, 4] 的和最大为 7。示例 3输入arr [] [5, -2, 3, 4]输出12解释环形子数组 [3, 4, 5] 的和最大为 12。二、【朴素解法】枚举所有可能的子数组 —— 时间复杂度 O (n²)空间复杂度 O (1)(一) 解法思路将每个元素视作子数组的起点计算从该起点出发所能得到的最大和其中既包含线性子数组也包含环形子数组。(二) 使用6种语言实现1. C#include iostream #include vector using namespace std; int maxCircularSum(vectorint arr) { int n arr.size(); int res arr[0]; // 以索引 i 为起点的子数组 for(int i 0; i n; i) { int currSum 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j 0; j n; j) { // 环形索引 int idx (i j) % n; currSum currSum arr[idx]; res max(res, currSum); } } return res; } int main() { vectorint arr {8, -8, 9, -9, 10, -11, 12}; cout maxCircularSum(arr); }2. C#include stdio.h int maxCircularSum(int arr[], int n) { int res arr[0]; // 以索引 i 为起点的子数组 for(int i 0; i n; i) { int currSum 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j 0; j n; j) { // 环形索引 int idx (i j) % n; currSum currSum arr[idx]; if (currSum res) { res currSum; } } } return res; } int main() { int arr[] {8, -8, 9, -9, 10, -11, 12}; int n sizeof(arr) / sizeof(arr[0]); printf(%d\n, maxCircularSum(arr, n)); return 0; }3. Javaclass DSA { static int maxCircularSum(int[] arr) { int n arr.length; int res arr[0]; // 以索引 i 为起点的子数组 for(int i 0; i n; i) { int currSum 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j 0; j n; j) { // 环形索引 int idx (i j) % n; currSum currSum arr[idx]; res Math.max(res, currSum); } } return res; } public static void main(String[] args) { int[] arr {8, -8, 9, -9, 10, -11, 12}; System.out.println(maxCircularSum(arr)); } }4. Pythondef maxCircularSum(arr): n len(arr) res arr[0] # 以索引 i 为起点的子数组 for i in range(n): currSum 0 # 遍历以索引 i 为起点的子数组的所有可能终点 for j in range(n): # 环形索引 idx (i j) % n currSum arr[idx] res max(res, currSum) return res if __name__ __main__: arr [8, -8, 9, -9, 10, -11, 12] print(maxCircularSum(arr))5. C#using System; class DSA { static int maxCircularSum(int[] arr) { int n arr.Length; int res arr[0]; // 以索引 i 为起点的子数组 for(int i 0; i n; i) { int currSum 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j 0; j n; j) { // 环形索引 int idx (i j) % n; currSum currSum arr[idx]; res Math.Max(res, currSum); } } return res; } static void Main() { int[] arr {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }6. JavaScriptusing System; class GfG { static int maxCircularSum(int[] arr) { int n arr.Length; int res arr[0]; // 以索引 i 为起点的子数组 for(int i 0; i n; i) { int currSum 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j 0; j n; j) { // 环形索引 int idx (i j) % n; currSum currSum arr[idx]; res Math.Max(res, currSum); } } return res; } static void Main() { int[] arr {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }(三)代码输出和算法复杂度输出22时间复杂度O(n^2)空间复杂度O(1)三、【优化解法】利用前缀和与后缀和 —— 时间复杂度 O (n)空间复杂度 O (n)(一) 解法思路在环形数组中最大子数组和要么是普通最大和非环形数组的最大子数组和要么是环形最大和同时包含数组开头和结尾元素的子数组和。普通最大和可以通过卡登算法Kadanes Algorithm高效求解。而环形最大和则通过前缀和与后缀和组合的方式计算。首先我们计算最大后缀和数组 maxSuffix其中 maxSuffix[i] 存储从大于等于 i 的任意索引开始的最大后缀和。随后遍历输入数组将截止到索引 i 的前缀和与索引 i1 处的最大后缀和相结合避免重复统计第 i 个元素以此计算环形子数组和并遍历所有 i 取值取最大值。(二) 使用6种语言实现1. C#include iostream #include vector using namespace std; int maxCircularSum(vectorint arr) { int n arr.size(); int suffixSum arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 vectorint maxSuffix(n 1, 0); maxSuffix[n - 1] arr[n - 1]; for(int i n - 2; i 0; i--) { suffixSum suffixSum arr[i]; maxSuffix[i] max(maxSuffix[i 1], suffixSum); } // circularSum 表示环形子数组的最大和 int circularSum arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum arr[0]; int currSum 0; int prefix 0; for(int i 0; i n; i) { // 卡登算法Kadanes algorithm currSum max(currSum arr[i], arr[i]); normalSum max(normalSum, currSum); // 计算最大环形和 prefix prefix arr[i]; circularSum max(circularSum, prefix maxSuffix[i1]); } return max(circularSum, normalSum); } int main() { vectorint arr {8, -8, 9, -9, 10, -11, 12}; cout maxCircularSum(arr); }2. C#include stdio.h #include stdlib.h int maxCircularSum(int arr[], int n) { int suffixSum arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 int* maxSuffix (int*)malloc((n 1) * sizeof(int)); maxSuffix[n - 1] arr[n - 1]; for(int i n - 2; i 0; i--) { suffixSum suffixSum arr[i]; if(maxSuffix[i 1] suffixSum) maxSuffix[i] maxSuffix[i 1]; else maxSuffix[i] suffixSum; } // circularSum 表示环形子数组的最大和 int circularSum arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum arr[0]; int currSum 0; int prefix 0; for(int i 0; i n; i) { // 卡登算法Kadanes Algorithm currSum (currSum arr[i] arr[i]) ? currSum arr[i] : arr[i]; normalSum (normalSum currSum) ? normalSum : currSum; // 计算最大环形和 prefix prefix arr[i]; if(circularSum prefix maxSuffix[i 1]) circularSum prefix maxSuffix[i 1]; } return (circularSum normalSum) ? circularSum : normalSum; } int main() { int arr[] {8, -8, 9, -9, 10, -11, 12}; int n sizeof(arr) / sizeof(arr[0]); printf(%d\n, maxCircularSum(arr, n)); return 0; }3. Javaimport java.util.Arrays; class DSA { static int maxCircularSum(int[] arr) { int n arr.length; int suffixSum arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 int[] maxSuffix new int[n 1]; maxSuffix[n - 1] arr[n - 1]; for(int i n - 2; i 0; i--) { suffixSum suffixSum arr[i]; maxSuffix[i] Math.max(maxSuffix[i 1], suffixSum); } // circularSum 表示环形子数组的最大和 int circularSum arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum arr[0]; int currSum 0; int prefix 0; for(int i 0; i n; i) { // 卡登算法Kadanes algorithm currSum Math.max(currSum arr[i], arr[i]); normalSum Math.max(normalSum, currSum); // 计算最大环形和 prefix prefix arr[i]; circularSum Math.max(circularSum, prefix maxSuffix[i 1]); } return Math.max(circularSum, normalSum); } public static void main(String[] args) { int[] arr {8, -8, 9, -9, 10, -11, 12}; System.out.println(maxCircularSum(arr)); } }4. Pythondef maxCircularSum(arr): n len(arr) suffixSum arr[n - 1] # maxSuffix 数组用于存储 # 目前为止的最大后缀和 maxSuffix [0] * (n 1) maxSuffix[n - 1] arr[n - 1] for i in range(n - 2, -1, -1): suffixSum arr[i] maxSuffix[i] max(maxSuffix[i 1], suffixSum) # circularSum 表示环形子数组的最大和 circularSum arr[0] # normalSum 表示 # 数组视为非环形时的最大子数组和 normalSum arr[0] currSum 0 prefix 0 for i in range(n): # 卡登算法Kadanes algorithm currSum max(currSum arr[i], arr[i]) normalSum max(normalSum, currSum) # 计算最大环形和 prefix arr[i] circularSum max(circularSum, prefix maxSuffix[i 1]) return max(circularSum, normalSum) if __name__ __main__: arr [8, -8, 9, -9, 10, -11, 12] print(maxCircularSum(arr))5. C#using System; class DSA { static int maxCircularSum(int[] arr) { int n arr.Length; int suffixSum arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 int[] maxSuffix new int[n 1]; maxSuffix[n - 1] arr[n - 1]; for(int i n - 2; i 0; i--) { suffixSum suffixSum arr[i]; maxSuffix[i] Math.Max(maxSuffix[i 1], suffixSum); } // circularSum 表示环形子数组的最大和 int circularSum arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum arr[0]; int currSum 0; int prefix 0; for(int i 0; i n; i) { // 卡登算法Kadanes algorithm currSum Math.Max(currSum arr[i], arr[i]); normalSum Math.Max(normalSum, currSum); // 计算最大环形和 prefix prefix arr[i]; circularSum Math.Max(circularSum, prefix maxSuffix[i 1]); } return Math.Max(circularSum, normalSum); } static void Main() { int[] arr {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }6. JavaScriptfunction maxCircularSum(arr) { let n arr.length; let suffixSum arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 let maxSuffix new Array(n 1).fill(0); maxSuffix[n - 1] arr[n - 1]; for(let i n - 2; i 0; i--) { suffixSum arr[i]; maxSuffix[i] Math.max(maxSuffix[i 1], suffixSum); } // circularSum 表示环形子数组的最大和 let circularSum arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 let normalSum arr[0]; let currSum 0; let prefix 0; for(let i 0; i n; i) { // 卡登算法Kadanes algorithm currSum Math.max(currSum arr[i], arr[i]); normalSum Math.max(normalSum, currSum); // 计算最大环形和 prefix arr[i]; circularSum Math.max(circularSum, prefix maxSuffix[i 1]); } return Math.max(circularSum, normalSum); } // 测试代码 const arr [8, -8, 9, -9, 10, -11, 12]; console.log(maxCircularSum(arr));(三)代码输出和算法复杂度输出22时间复杂度O(n)空间复杂度O(n)四、【最优解法】使用卡登算法Kadane 算法—— 时间复杂度 O (n)空间复杂度 O (1)(一) 解法思路这种方法与前一种思路类似但核心区别在于我们同样使用卡登算法Kadanes Algorithm来计算环形子数组的最大和。环形子数组的最大和可以定义为数组的总和减去数组中间某一段子数组的和。因此想要最大化环形子数组的和就需要最小化中间这段子数组的和。环形数组最大子数组和数组总和 - 最小子数组和。如果最小子数组和等于数组总和则返回普通最大子数组和。因为当数组所有元素均为负数时环形和会是 0但正确答案只能是负数。(二) 使用6种语言实现1. C#include iostream #include vector using namespace std; int maxCircularSum(vectorint arr) { int totalSum 0; int currMaxSum 0, currMinSum 0; int maxSum arr[0], minSum arr[0]; for (int i 0; i arr.size(); i) { // 卡登算法求最大子数组和 currMaxSum max(currMaxSum arr[i], arr[i]); maxSum max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum min(currMinSum arr[i], arr[i]); minSum min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum totalSum arr[i]; } int normalSum maxSum; int circularSum totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if (minSum totalSum) return normalSum; return max(normalSum, circularSum); } int main() { vectorint arr {8, -8, 9, -9, 10, -11, 12}; cout maxCircularSum(arr); }2. C#include stdio.h int maxCircularSum(int arr[], int n) { int totalSum 0; int currMaxSum 0, currMinSum 0; int maxSum arr[0], minSum arr[0]; for(int i 0; i n; i) { // 卡登算法求最大子数组和 currMaxSum (currMaxSum arr[i] arr[i]) ? currMaxSum arr[i] : arr[i]; maxSum (maxSum currMaxSum) ? maxSum : currMaxSum; // 卡登算法求最小子数组和 currMinSum (currMinSum arr[i] arr[i]) ? currMinSum arr[i] : arr[i]; minSum (minSum currMinSum) ? minSum : currMinSum; // 输入数组所有元素的总和 totalSum arr[i]; } int normalSum maxSum; int circularSum totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if(minSum totalSum) return normalSum; return (normalSum circularSum) ? normalSum : circularSum; } int main() { int arr[] {8, -8, 9, -9, 10, -11, 12}; int n sizeof(arr) / sizeof(arr[0]); printf(%d\n, maxCircularSum(arr, n)); return 0; }3. Javaclass DSA { static int maxCircularSum(int[] arr) { int totalSum 0; int currMaxSum 0, currMinSum 0; int maxSum arr[0], minSum arr[0]; for(int i 0; i arr.length; i) { // 卡登算法求最大子数组和 currMaxSum Math.max(currMaxSum arr[i], arr[i]); maxSum Math.max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum Math.min(currMinSum arr[i], arr[i]); minSum Math.min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum arr[i]; } int normalSum maxSum; int circularSum totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if(minSum totalSum) return normalSum; return Math.max(normalSum, circularSum); } public static void main(String[] args) { int[] arr {8, -8, 9, -9, 10, -11, 12}; System.out.println(maxCircularSum(arr)); } }4. Pythondef maxCircularSum(arr): totalSum 0 currMaxSum 0 currMinSum 0 maxSum arr[0] minSum arr[0] for i in range(len(arr)): # 卡登算法求最大子数组和 currMaxSum max(currMaxSum arr[i], arr[i]) maxSum max(maxSum, currMaxSum) # 卡登算法求最小子数组和 currMinSum min(currMinSum arr[i], arr[i]) minSum min(minSum, currMinSum) # 输入数组所有元素的总和 totalSum arr[i] normalSum maxSum circularSum totalSum - minSum # 如果最小子数组和等于总和 # 则直接返回普通最大子数组和 if minSum totalSum: return normalSum return max(normalSum, circularSum) if __name__ __main__: arr [8, -8, 9, -9, 10, -11, 12] print(maxCircularSum(arr))5. C#using System; class DSA { static int maxCircularSum(int[] arr) { int totalSum 0; int currMaxSum 0, currMinSum 0; int maxSum arr[0], minSum arr[0]; for(int i 0; i arr.Length; i) { // 卡登算法求最大子数组和 currMaxSum Math.Max(currMaxSum arr[i], arr[i]); maxSum Math.Max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum Math.Min(currMinSum arr[i], arr[i]); minSum Math.Min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum arr[i]; } int normalSum maxSum; int circularSum totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if(minSum totalSum) return normalSum; return Math.Max(normalSum, circularSum); } static void Main() { int[] arr {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }6. JavaScriptfunction maxCircularSum(arr) { let totalSum 0; let currMaxSum 0, currMinSum 0; let maxSum arr[0], minSum arr[0]; for (let i 0; i arr.length; i) { // 卡登算法求最大子数组和 currMaxSum Math.max(currMaxSum arr[i], arr[i]); maxSum Math.max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum Math.min(currMinSum arr[i], arr[i]); minSum Math.min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum arr[i]; } let normalSum maxSum; let circularSum totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if (minSum totalSum) return normalSum; return Math.max(normalSum, circularSum); } // 测试代码 const arr [ 8, -8, 9, -9, 10, -11, 12 ]; console.log(maxCircularSum(arr));(三)代码输出和算法复杂度输出22时间复杂度O(n)空间复杂度O(1)