java - n 个数字排列成一个圆圈。我们需要找到连续编号的最大总和

Question

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

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

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

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

Answer 1

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

并找到长度不超过原圆的最大子数组。

Answer 2

或者，不是复制数组，而是将索引变量的范围从0..n-1to扩展到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;
}