n个数字排成一个圆圈。 我们需要找到连续nos的最大总和

对于线性arrays，找到连续nos的最大总和的问题。 简单。 可以通过使用Kadane的Algo轻松完成。 。 但是现在arrays是圆形的，我们需要找到连续nos的最大总和。 因此startindex和endindex可以在数组中的任何位置。 我没有得到如何在O(n)时间内解决它。

例如： { 8, 9, -14, 4, 3} 。

最大子arrayssum= 4+3+8+9= 24. startindex=3 and endindex=1 （零索引数组）。 请给我一些关于如何处理这个问题的提示或算法。 无需代码。

编辑：正如大家所提到的，圆形数组类似于跨越两次的相同数组。 但是如何在该arrays上应用Kadane的Algo并限制连续的nos。 到<= n

Answer 1

复制数组一次以获得{ 8, 9, -14, 4, 3, 8, 9, -14, 4, 3} ，

并找到其长度不超过原始圆的最大子arrays。

Answer 2

或者，不是复制数组，而是将索引变量的范围从0..n-1扩展到0..2n-1并使用(x mod n)而不是x作为索引。

Answer 3

1. 这个概念是通过Kadane算法找到最大和。
2. 然后通过否定元素找到Kadane算法的最小和，并将其添加到数组的总和中。

比打印步骤1和步骤2计算的元素的最大值。

 private static int maxCircularSum(int a[]) { int max_kadane = kadane(a); int max_wrap = 0, i; for (i = 0; i < a.length; i++) { max_wrap += a[i]; // Calculate array-sum a[i] = -a[i]; // invert the array (change sign) } max_wrap = max_wrap + kadane(a); return (max_wrap > max_kadane) ? max_wrap : max_kadane; } private static int kadane(int[] a) { int max = Integer.MIN_VALUE, sum = 0; for (int k : a) { sum = sum + k; if (sum < 0) { sum = 0; } if (max < sum) { max = sum; } } return max; }