maximum contiguous sum in a circular buffer

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;

}

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.

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

See the following link :

It solves a problem using Kadane Algorithem.

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