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

Question

对于线性数组，找到连续数的最大和的问题很容易。可以使用Kadane的Algo轻松完成。。但现在数组是圆形的，我们需要找到连续编号的最大和。因此startindex和endindex可以在数组中的任何位置。我不知道如何在O(n)时间内解决它。

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

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

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

Answer 1

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

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

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;
}