n个被布置在一个圆。 我们需要找到连续编号的最大总和(n numbers are arrange

对于线性阵列，发现连续号的最大总和的问题。 简单。 可以通过使用可以轻松完成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-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;
}

文章来源: n numbers are arranged in a circle. We need to find the maximum sum of consecutive nos