CareerCup

#include<iostream.h>
#include<conio.h>
int getmaxsum(int *a,int l)
{
int maxsum = 0;
int runningsum = 0;
int size = 2 *l;
for(int i=0; i < size-1; i++)
{
runningsum += a[i%l];
if(maxsum < runningsum)
maxsum = runningsum;
else if(runningsum < 0)
runningsum = 0;
}
return maxsum;
   }
int main()
{
int b[20] = {8,-8,9,-9,10,-11,12};
cout<<"maxsum is :";
int s = getmaxsum(b,7);
cout<< s;
getch();
return 0;  
 }

Circular Kadane.

#include <stdio.h>
#include <stdlib.h>

/* Circular kadane with limited size */
int maxSum ( int arr[], int size ) {
  int i, tSize = (size<<1) - 1 ;
  int maxsum, sumsofar, ti ;
  int *dup_arr = (int *) malloc (sizeof(int)*tSize) ;
  if ( size == 0 )
    return 0 ;
  for ( i = 0 ; i < size ; i ++ )
    dup_arr[i] = arr[i] ;
  for ( ; i < tSize ; i ++ )
    dup_arr[i] = arr[i-size] ;

  maxsum = dup_arr[0];
  sumsofar = dup_arr[0] ;
  ti = 0 ;
  for ( i = 1 ; i < tSize ; i ++ ) {
    //printf ( "\nBefore op : sumsofar = %d, maxsum = %d, i = %d, ti = %d", sumsofar, maxsum, i, ti ) ;
    /* Check for resetting the lower limit */
    if ( sumsofar <= 0 ) {
      sumsofar = 0 ;
      ti = i + 1;
    }
    /* Check for the array size : calculation should be with in array size*/
    if ( i-ti >= size ) {
      //printf ( "\nsize exceeded.");
      ti = i ;
      sumsofar = 0 ;
    }
    sumsofar += dup_arr[i] ;

    /* renew the maximum sum */
    if ( sumsofar > maxsum )
      maxsum = sumsofar ;
  }
  free (dup_arr) ;
  return maxsum ;
}

int main () {
  int arr[] = {1,1,1,1,1,1,1} ;
  printf ( "\nMax sum is : %d", maxSum (arr, (sizeof(arr)/sizeof(arr[0])) ) ) ;
  return 0 ;
}

// Dont Understand what Circular Array make to the problem,
For an Array this is following solution in C#

// Try for O(n)
        public int GetMaxSubArray(int[] input)
        {
            // Error Case : No item in the input
            if (input == null || input.Length == 0)
            {
                return 0;
            }

            // Early Exit : If one item is present that is the Maximum
            if (input.Length == 1)
            {
                return input[0];
            }

            // For more than 1 element in the array we need to Process the array to get the Max Sub Array
            // Take first item as the current Max
            int currentMax = 0;
            int maxEnding = 0;

            for (int index = 0; index < input.Length; index++)
            {
                // Calculate the current Sum
                maxEnding = Math.Max(input[index], maxEnding + input[index]);
                currentMax = Math.Max(currentMax, maxEnding);

                Trace.WriteLine(string.Format("Sum from Index {0} SumEndingHere : {1}, MaxSum : {2}", index, maxEnding, currentMax));
            }

            return currentMax;
        }

Let me know if there is something about Circular Array that i need to handle

keep adding the numbers form i = 1 till n and with subsequent add keep storing the the sum and comapre this sum with every consecutive add.
if sum (current -1)< sum(current)
sum(current - 1) = sum (current)


I too was asked this question , I was also asked to find the numbers which will make that sum.
I made it to complex by answerng it correctly.

#include <stdio.h>

int A[7]={8,-8,9,-9,10,-11,12};

int maxConsecutiveSum(int A[], int N, int *start, int* len){
     
     int max=0;
     
     for(int i=0;i<N;i++) {
            
         for ( int j =0; j <N;j++) {
            
             int sum=0;
             for(int k =j; k <i+j; k++) {
                 sum=sum+A[k%N];        
                     
             }    
             if(sum>max) {
            
                 max=sum;            
                 *start=j;
                 *len=i;
             }
         }        
             
     }           
     return (max);
}

int main(){
    int start=0,len=0;
     int s = maxConsecutiveSum(A,7,&start,&len);  
     printf("max sum is =%d start element is %d and length is %d\n",s,start,len); 
    
    getchar();
}

Output:
1
max sum is =22 start element is 6 and length is 6

The above code can be found at
codepad.org/vEm3kD2l

/**
 * Write a description of class ConsecutiveSum here.
 * 
 * @author (your name) 
 * @version (a version number or a date)
 */
public class ConsecutiveSum
{
   public static void main(int [] a)
   {
       int [] leftMax = new int[a.length];
       int  [] rightMax = new int[a.length];
       int max=0;
       if(a[0]+a[a.length -1] > 0)
       {
           leftMax[0]=rightMax[a.length-1]=a[0]+a[a.length -1];
       }
       for(int i =1;i< a.length-1 ;i++)
       {
           if(leftMax[i-1]+a[i] >= 0) leftMax[i]= leftMax[i-1]+a[i];
           else leftMax[i]=a[i];
           if(max < leftMax[i]) max= leftMax[i];
       }
       
       for(int i =a.length-2;i >0; i--)
       {
           if(rightMax[i]+a[i] >= 0) rightMax[i-1]= rightMax[i]+a[i];
           else rightMax[i]=a[i];
           if(max < rightMax[i-1]) max= rightMax[i-1];
       }
       
       
      
      
       System.out.println(max);
   }
}

How about dynamic programming?
first of all, concatenate the array by itself to simulate the circle
for each node i, maintain two maximum: the max sum of consecutive nos between [0,i] and the max sum of consecutive nos ended at i.
then for the last node, its max sum will be either one of them
note the constraint that the sequence length must be smaller than n
to identify the consecutive nos, just maintain the index of the consecutive nos at each node

it seems to be an O(n) algorithm but still a little complicated.

source code from 
http://www.geeksforgeeks.org/archives/576
#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
   int max_so_far = 0, max_ending_here = 0;
   int i;
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
     if(max_ending_here < 0)
        max_ending_here = 0;
     if(max_so_far < max_ending_here)
        max_so_far = max_ending_here;
    }
    return max_so_far;
} 
 
/*Driver program to test maxSubArraySum*/
int main()
{
   int a[] = {8,-8,9,-9,10,-11,12,8,-8,9,-9,10,-11,12};//append the array once more to end of array.
   int max_sum = maxSubArraySum(a, 13);
   printf("Maximum contiguous sum is %d\n", max_sum);
   getchar();
   return 0;
}

Kadane's algorithm

def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

taken from Wikipedia - Maximum subarray problem

public class CircularMaxSubArraySum {
    /**
     * Compute max sub-array sum using Kadane - (1).
     * Compute min sub-array sum using Kadane by negating values - (2).
     * Return max of '(1)' and 'SUM_ELEMENTS - (2)'.
     */
    static int findMaxSubArraySum(int a[]) {
        int sum = 0;
        int maxPos = Integer.MIN_VALUE, currPos = 0; // computes max sub-array
        int maxNeg = Integer.MIN_VALUE, currNeg = 0; // computes min sub-array
        for (int i = 0; i < a.length; ++i) {
            sum += a[i];
            currPos += a[i];
            if (maxPos < currPos) {
                maxPos = currPos;
            }
            if (currPos <= 0) {
                currPos = 0;
            }

            currNeg += -a[i];
            if (maxNeg < currNeg) {
                maxNeg = currNeg;
            }
            if (currNeg <= 0) {
                currNeg = 0;
            }
        }
        // Case where there were no positive numbers
        if (maxPos <= 0) {
            return maxPos;
        }
        maxNeg = sum + maxNeg;
        return (maxPos > maxNeg) ? maxPos : maxNeg;
    }

    public static void main(String[] args) {
        System.out.println(
            findMaxSubArraySum(new int[]{-8, 9, -11, 12, -10, 100, -1000}));
        System.out.println(
            findMaxSubArraySum(new int[]{-8, -9, -11}));
        System.out.println(
            findMaxSubArraySum(new int[]{8, -8, 9, -9, 19, -11, 12}));
    }
}

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n; //enter number of element
int a[n],i;
for(i=0;i<n;i++)
cin>>a[i];
int mf=0,tm=0,ts=0,tf=0,sf=0,ef=0;
for(i=0;i<n;i++)
{
tm+=a[i];
if(tm<0)
{
tm=0;
ts=i+1;
tf=i+1;
}
else
if(tm>=mf)
{
mf=tm;
sf=ts;
ef=tf;
}
else
tf=i;
}
//cout<<mf<<" "<<sf<<" ";
for(i=0;i<sf&&i<n;i++)
{
tm+=a[i];
if(tm<0)
tm=0;
else
if(tm>mf)
mf=tm;
}
cout<<mf;
}

1. Duplicate the array so that it become {8,-8,9,-9,10,-11,12,8,-8,9,-9,10,-11,12}
2. Now add consecutive n elements starting from 1st element till nth element. in every case if Max Value < addedValueForNth, change the MaxValue
3. Return MaxValue

public class Test {

static int A[]={8,-8,9,-9,10,-11,12};

public static int maxConsecutiveSum(int A[], int N){
int start = 0;
int end = N;
int sum = 0;
int maxSum = 0;
int maxSumIndex = 0;
int i=start;
while(i != end) {
sum = sum + A[i];
if(sum > maxSum ) {
maxSum = sum;
maxSumIndex = start;
}
if (sum <= 0) {
end = start -1;
if (end < 0) end = end + N;
start = i+1;
i = start;
sum = 0;
continue;
}
i++; if (i == N) i=0;
}
System.out.println("max sum is =" + maxSum + "start element is" + maxSumIndex);
return maxSum;
}

/**
* @param args
*/
public static void main(String[] args) {
maxConsecutiveSum(A,7);
}

}

Ignore previous comment, this is the solution, cheers

public class Test {

static int A[]={8,-8,9,-9,10,-11,12};

public static int maxConsecutiveSum(int A[], int N){
int start = 0;
int end = N;
int sum = 0;
int maxSum = 0;
int maxSumIndex = 0;
int i=start;
while(i != end) {
sum = sum + A[i];
if(sum > maxSum ) {
maxSum = sum;
maxSumIndex = start;
}
if (sum < 0) {
end = start -1;
if (end < 0) end = end + N - 1;
start = i+1;
i = start;
sum = 0;
continue;
}
i++; if (i == N) i=0;
}
System.out.println("max sum is =" + maxSum + "start element is" + maxSumIndex);
return maxSum;
}

/**
* @param args
*/
public static void main(String[] args) {
maxConsecutiveSum(A,7);
}

}

Output : max sum is =22start element is6

Can't we just find the min_sum of consecutive numbers similar to Kadane's algorithm and subtract it from total sum ??

Solve it for with normal array with the following modification:
geeksforgeeks.org/archives/576

Now treat circular array as special case, when the last element is seen if the sum including the last element is positive continue with the first element and break when the sum goes negative.

// this shud work

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a;
int max_sum(int size)
{  
   int summ,maxx,i,z,temp=0;
   summ=maxx=a[0];
   for(i=1;i<size;i++)
   {   if(summ<0)      summ=a[i];
       else            summ+=a[i];
       if(i==size-1)   temp=summ;  
       maxx=max(summ,maxx);     
   }
   if(temp>0)
   {      for(--size;temp;temp-=a[size--]);
          
          maxx=summ;
          for(i=0;i<=size;i++)
          {   if(summ<0)      summ=a[i];
              else            summ+=a[i];
              maxx=max(summ,maxx);     
          }
   }
   return maxx;
}  
main()
{
    int n,x,i;
    cin>>n;
    for(i=0;i<n;i++)  cin>>x , a.push_back(x);
    for(i=0;i<n;i++)  cout<<a[i]<<" ";         cout<<endl;
    printf("%d\n",max_sum(a.size()));
    //system("pause");
    return 0;
}

A simple O(n) solution- suppose {-3,5,-6,6,7,8}
1.let start point is i=0; identify end point and the sum..in this case endpoint=5,sum17;
2.now loop from i=1 to i=n-1;
if(a[i-1]>0) sum2=sum2+a[i-1];
if(a[i-1]<0) and strart index=i-1; strat index=i sum=sum-a[i-1];
if(a[i-1]<0)and strat index !=i-1 ;sum2=sum2+a[i-1];if(sum2<0)start index=i;and sum2=0;
so sum and startinedx and endindex return everything in O(n) hopefully.....i covered all type testcases

A simple O(n) solution- suppose {-3,5,-6,6,7,8}
1.let start point is i=0; identify end point and the sum..in this case endpoint=5,sum17;
2.now loop from i=1 to i=n-1;
if(a[i-1]>0) sum2=sum2+a[i-1];
if(a[i-1]<0) and strart index=i-1; strat index=i sum=sum-a[i-1];
if(a[i-1]<0)and strat index !=i-1 ;sum2=sum2+a[i-1];if(sum2<0)start index=i;and sum2=0;
so sum and startinedx and endindex return everything in O(n) hopefully.....i covered all type testcases

#include<stdio.h>
#include<conio.h>
int main()
{ int a[]={8,-8,9,-9,10,-11,12};
int start,maxstart,maxend,sum=0,max=0,i;
for(i=0;i<7;i++)
{ if(sum==0)
start=i;
if(sum+a[i]<0)
sum=0;
else sum=sum+a[i];
if(sum>max)
{ maxstart=start;
maxend=i;
max=sum;
}
}
for(i=0;i<start;i++)
{ if(sum==0)
break;
if(sum+a[i]<0)
sum=0;
else sum=sum+a[i];
if(sum>max)
{ maxstart=start;
maxend=i;
max=sum;
}
} printf("the maximum sum of the array is....%d \nstart= %d end= %d"
,max,maxstart,maxend);
getch();
return 0;

}

#include<stdio.h>
main()
{
int a[]={1,2,-3,4,-6,8,9,2,100,-50};
int i,tmp=0,max=a[0],index=0,t_id=0;
int l=sizeof(a)/sizeof(a[0]),flip=1;
for(i=0;i<l;i++){
tmp=tmp+a[i];
if(max<tmp){
max=tmp;
index=t_id;
}
if(tmp<0){
tmp=0;
t_id=i+1;
}
if(flip && tmp>0 && i==l-1)
{
l=index;
flip=0;
i=-1;
}
}


printf("%d",max);
}

awesomecoder.blogspot.com/2012/08/maximum-contiguous-sum-in-circular-array.html

public class CircularKadane {

public int getMaxSum(int[] a) {

int maxSum = Integer.MIN_VALUE;
int tempSum = 0;
int stop = 0;

for (int i = 0; i < a.length * 2 - 1; i++) {
int index = i % a.length;
if (i >= a.length && index >= stop)
break;
tempSum += a[index];
if (maxSum < tempSum) {
maxSum = tempSum;
}
if (tempSum < 0) {
tempSum = 0;
stop = i + 1;
}
}

return maxSum;
}

public static void main(String[] args) {
// TODO Auto-generated method stub

CircularKadane c = new CircularKadane();
int[] a = { 8, -8, 9, -9, 10, -11, 12 };
System.out.println(c.getMaxSum(a));

int[] b = { 1, 1, 1, 1, 1, 1, 1 };
System.out.println(c.getMaxSum(b));

int[] d = { 1, -1, 2, -1, 1 };
System.out.println(c.getMaxSum(d));
}

}

1. First duplicate the input array
2. Use the same approach as if you are solving the array version of this problem. That means iterate through the array and keep a running sum. Add this sum to current element and compare that to the current maximum. If sum < 0 then reset it to 0.
3. Avoid including an element in the running sum twice by keeping track of the starting index of the running sum, and subtracting the element at the starting index from the running sum if necessary.

int maxSum(int[] circle) {
	int len = circle.length;
	// duplicate the input "array"
	int[] arr = new int[2*len];
	System.arraycopy(circle, 0, arr, 0, len);
	System.arraycopy(circle, 0, arr, len, len);

	int max = Integer.MIN_VALUE;
	int start = 0;
	int curr = 0;

	for(int i=0; i<2*len; i++) {
		curr += arr[i];
		if(i - start >= len) {
			curr-=arr[start++];
		}
		if(curr > max) {
			max = curr;
		} else if(curr < 0){
			curr = 0;
		}
		if(curr == 0)
			start = i+1;
	}
	return max;
}

public static void main(String[] args) {

		int[] arr = {1,-1,2,-1,1};
		//int[] arr =  {8,-8,9,-9,10,-11,12};
		int max = Integer.MIN_VALUE;
		int start = 0;
		int end = 0;
		int sum = 0;

		int curr = 0 ;

		while(true){

			if(sum < 0){

				sum = 0;
				start = curr;

			}

			sum += arr[curr];
			if(sum >= max ){
				max = sum;
				end = curr;
			}


			curr++;
			if(curr  >= arr.length){
				curr = curr % arr.length;
				
			}
			if(curr == start){ 
				if(start == arr.length-1){
				break;
				}else{
					++start;
					curr = start;
					sum=0;
					
				}
			}
		}
		
		System.out.println(max);
		System.out.println(start);
		System.out.println(end);
	}

public static int maxCirSubarray(int[] array) {
		int kadane_max = kadane(array);
		int corner_case_max = 0;
		for (int i = 0; i < array.length; i++) {
			corner_case_max += array[i];
			array[i] = -array[i];
		}
		corner_case_max += kadane(array);
		return (kadane_max > corner_case_max) ? kadane_max : corner_case_max;
	}

	public static int kadane(int[] array) {
		if (array == null || array.length == 0) {
			return 0;
		}
		int max_so_far = 0;
		int max_ending_here = 0;
		for (int i = 0; i < array.length; i++) {
			max_ending_here += array[i];
			if (max_ending_here < 0) {
				max_ending_here = 0;
			}
			if (max_ending_here > max_so_far) {
				max_so_far = max_ending_here;
			}
		}
		return max_so_far;
	}