# 最大循環子數組總和 > 原文： [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 ```