maximum contiguous sum in a circular buffer

I have a program to determine the largest contiguous sum in an array, but want to extend it to work with circular arrays. Is there an easier way to do that than doubling the single array and calling my function to find the largest sum over all n-length arrays in the 开发者_JS百科2n length array?

See the following link :

It solves a problem using Kadane Algorithem.

http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

I think the solution by @spinning_plate is wrong. Ca you please test it for the given cases.

int arr[] = {-3, 6, 2, 1, 7, -8, 13, 0};

Your approach returns 21.

Actual solution can be start from 6th index(i.e. 13 value) .. and end to 4th index(i.e. 7 value). Since array is circular we can take continuous series from 6th index to 7th index and from 0th index to 4th index.

The actual answer for the above case is : 26

Well, you don't have to actually double the array. You can just emulate it by indexing your existing array modulo n, or by just iterating over it twice. Depending on the size of your array and cache behavior, this should be at most a factor of two slower than the algorithm for the noncircular array.

For the given problem, We will apply kadane algorithm and we will also find the subset which will have maximum negative value.If the maximum negative value is removed that will give the sum of the remaining array in circular order.If that sum is greater than maximum sum then maximum sum will be sum in circular order. Complexity for the algorithm is O(n).

Eg:- arr[i]={10,-3,-4,7,6,5,-4,-1}
      Ans:  max_sum=7+6+5+(-4)+(-1)+10
            Removed_set={-3,-4}
int find_maxsum(int arr[],int n)
{
 int i=0;
 int total=0;
 int maxa=0;
 int mini=0;
 int min_sum=0;
 int max_sum=0;


 while(i<n) 
  {
    maxa=maxa+arr[i];
    total=total+arr[i];
    mini=mini+arr[i];

   if(maxa>max_sum)
     max_sum=maxa; 
   if(mini<min_sum)
     min_sum=mini;
   if(maxa<0)
     maxa=0;
   if(mini>=0)
    mini=0;
}
if(total-min_sum>max_sum)
   max_sum=total-min_sum;
 return max_sum;

}

I assume you are using the O(n) algorithm that continues adding to the sum, keeping track of the maximum, only restarting if you sum to a negative number. The only thing you need to do to capture the case of circular arrays is to apply the same principle to the circular aspect. When you reach the end of the array in the original algorithm, keep looping around to the start until you go below the maximum or hit the beginning of the current range (I think this is impossible, though, because if the solution was the full array, we sould have seen this on the first pass), in which case you're done.

max_start=0; max_end =0; maxv = 0; sum 0;
for i in range(arr):
    sum+= arr[i];
    if sum<0:
       sum=0; max_start =i;
    if maxv<sum:
       maxv=sum; max_end = i;

#seocnd pass
for i in range(max_start):
    sum+= arr[i];
    if sum<0:
       break;
    if maxv<sum:
       maxv=sum;max_end = i;

Correct code based on nikhil's idea: elements of the minimum sum sub-array cannot appear in the final wrapping-or-not maximum sum sub-array.

public int maxSum(int[] arr) {
    if (arr.length == 0) return 0;

    int sum = 0;
    int min = Integer.MAX_VALUE;
    int eix = 0;
    for (int i = 0; i < arr.length; i++) {
        sum = sum + arr[i] < arr[i] ? sum + arr[i] : arr[i];
        if (sum < min) {
            min = sum;
            eix = i;
        }
    }
    int max = 0;
    sum = 0;
    for (int i = eix; i < arr.length + eix; i++) {
        int ix = i < arr.length ? i : i - arr.length;
        sum = sum + arr[ix] > arr[ix] ? sum + arr[ix] : arr[ix];
        max = max > sum ? max : sum;
    }

    return max;
}

This code returns the correct answer even if all numbers are negative e.g., {-1, -2, -3}. will return -1;

 public static int maxSubarraySumCircular(int[] A) {

    int maxSum = Arrays.stream(A).max().getAsInt();
    if (maxSum < 0)
        return maxSum;

    int maxKadane = KadaneAlgorithm(A);
    int maxWrap = 0;
    for (int i = 0; i < A.length; i++) {
        maxWrap += A[i];
        A[i] = -A[i];
    }
    maxWrap = maxWrap + KadaneAlgorithm(A);

    return maxWrap > maxKadane ? maxWrap : maxKadane;
}

private static int KadaneAlgorithm(int[] A) {
    int maxSoFar = 0;
    int maxEndingHere = 0;
    for (int i = 0; i < A.length ; i++) {

        maxEndingHere = maxEndingHere + A[i];

        if (maxEndingHere < 0 )
            maxEndingHere = 0;

        if(maxSoFar < maxEndingHere)
            maxSoFar = maxEndingHere;
    }

    return maxSoFar;
}