n numbers are arranged in a circle. We need to fin

问题:

For a linear array, the problem of finding maximum sum of consecutive nos. is easy. Can be easily done by using Kadane's Algo.. But now the array is in the form of circle and we need to find the maximum sum of consecutive nos. So the startindex and endindex can be anywhere in the array. I am not getting how to solve it in O(n) time.

Eg: { 8, 9, -14, 4, 3} .

Maximum subarray sum= 4+3+8+9= 24. startindex=3 and endindex=1 (zero index array). Please give me some hint or algo on how to approach this problem. No code required.

EDIT: As everyone mentioned, a circular array is similar to same array spanning twice. But how to apply Kadane's Algo on that array and restricting the consecutive nos. to <=n

回答1:

copy the array once to obtain { 8, 9, -14, 4, 3, 8, 9, -14, 4, 3},

and find the maximum subarray whose length doesn't exceed the original circle.

回答2:

Or, rather than copy the array, extend the range of the index variable from 0..n-1 to 0..2n-1 and use (x mod n) instead of x as the index.

回答3:

1. The concept is to find the max sum by Kadane's algorithm.
2. Then find the min sum by Kadane's algorithm by negating the elements and add this to total sum of array.

Than print the maximum of the elements calculated by step 1 and step 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;
}