最大循环子数组总和 · GeeksForGeeks 中文系列教程

# 最大循环子数组总和 > 原文： [https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/](https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/) 给定 n 个数字（`+ve`和`-ve`），它们排列成一个圆圈，找出连续数字的最大和。例子： ``` Input: a[] = {8, -8, 9, -9, 10, -11, 12} Output: 22 (12 + 8 - 8 + 9 - 9 + 10) Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1} Output: 23 (7 + 6 + 5 - 4 -1 + 10) Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1} Output: 52 (7 + 6 + 5 - 4 - 1 - 1 + 40) ``` 最大和可以有两种情况： **情况 1**：排列有助于最大和的元素，使其中不存在换行。示例：`{-10, 2, -1, 5}`，`{-2, 4, -1, 4, -1}`。在这种情况下， [Kadane 的算法](https://www.geeksforgeeks.org/archives/576)将产生结果。 **情况 2**：排列有助于最大和的元素，使其位于其中。示例：`{10, -12, 11}`，`{12, -5, 4, -8, 11}`。在这种情况下，我们将换行更改为不换行。让我们看看如何。包装有贡献的元素意味着不包装无贡献的元素，因此请找出无贡献的元素的总和，然后从总和中减去该总和。要找出无贡献的总和，请反转每个元素的符号，然后运行 Kadane 的算法。我们的数组就像一个圆环，我们必须消除最大连续负值，这意味着倒置数组中的最大连续正值。最后，我们比较两种情况下获得的总和，并返回两个总和的最大值。感谢 ashishdey0 建议这种解决方案。以下是上述方法的 C/C++ ，Java 和 Python 实现。 ## C++ ```cpp // C++ program for maximum contiguous circular sum problem #include <bits/stdc++.h> using namespace std; // Standard Kadane's algorithm to // find maximum subarray sum int kadane(int a[], int n); // The function returns maximum // circular contiguous sum in a[] int maxCircularSum(int a[], int n) { // Case 1: get the maximum sum using standard kadane' // s algorithm int max_kadane = kadane(a, n); // Case 2: Now find the maximum sum that includes // corner elements. int max_wrap = 0, i; for (i = 0; i < n; i++) { max_wrap += a[i]; // Calculate array-sum a[i] = -a[i]; // invert the array (change sign) } // max sum with corner elements will be: // array-sum - (-max subarray sum of inverted array) max_wrap = max_wrap + kadane(a, n); // The maximum circular sum will be maximum of two sums return (max_wrap > max_kadane)? max_wrap: max_kadane; } // Standard Kadane's algorithm to find maximum subarray sum // See https://www.geeksforgeeks.org/archives/576 for details int kadane(int a[], int n) { int max_so_far = 0, max_ending_here = 0; int i; for (i = 0; i < n; i++) { max_ending_here = max_ending_here + a[i]; if (max_ending_here < 0) max_ending_here = 0; if (max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far; } /* Driver program to test maxCircularSum() */ int main() { int a[] = {11, 10, -20, 5, -3, -5, 8, -13, 10}; int n = sizeof(a)/sizeof(a[0]); cout << "Maximum circular sum is " << maxCircularSum(a, n) << endl; return 0; } // This is code is contributed by rathbhupendra ```