CareerCup

We can change the problem to this: give you 2*n numbers, query you that the maximum sum of less than n contiguous number.
Then we can solve it as follows:
We can use a queue and keep its length < n and keep the sum of numbers in it > 0. We know that a queue has a head and a tail. then we push these 2*n number one by one, the new number push to head, in order to maintain the queue's length < n and keep the sum in it > 0, we can delete number from tail, until satisfy the rule we make. Every time we push a number we can get a sum, the answer is the max{sum}. The computational complexity is O(2*n).
My english is poor, if you still have problem, please contact me through my
E-mail:hzshuai@gmail.com

Is there any specific reason for choosing the circle in this question?

Time complexity : O(n)
working code!
int sum=0,in1=-1,negative=-(-1)*2<<(sizeof(int)*8 -1) -1;
for(int i=0;i<n;i++)
{
if(sum+v[i]< sum)
{
sum=0;
in1=-1;
if(negative < sum + v[i]) negative=sum+v[i];
}
else
{
if(in1<0)in1=i;
sum +=v[i];
}
}
if(in1!=0)
{
for(int i=0;i<n;i++)
{
if(sum+v[i]< sum)
{
if(negative< sum+v[i])
negative=sum+v[i];
break;
}
else
{
sum +=v[i];

}
}
}
if(sum==0)
cout<<negative<<"\n";
else cout<<sum<<"\n";

Please correct me if I am wrong. Keep a variable max for updating it and a variable sum to keep the current sum, now start with any value on the circle, and add it to sum, if value of sum becomes less than to zero because of addition of any new element, make sum = 0 else continue, and again start adding elements to sum , while doing this just keep updating the "max" value. We will need to do this nearly 2 times on the circle, also make sure that the same element doesn't get added twice.

Cant we break the circle into a linear array and proceed in the same way as in normal max subsequence problem?
We will have to alter the logic like: two elements A and B can be a part of solution iff
1) index of A and B are adjacent.
2) index of A and B are the indices of first and last elements of array (so as to complete the circular coverage).

<pre lang="" line="1" title="CodeMonkey18054" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}


int MaximumContigiousSumInACircle(int *A, int *n)
{
int MaxSumInRegularArray = MaximumContigiousSum(A,n);
int MaxContigiousSumFromZeroInARun = A[0], MaxContigiousSumFromZero = 0, FirstIndex = 0;
for(int i = 1; i < n; i++)
{
if(MaxContigiousSumFromZeroInARun + A[i] > A[i])
{
MaxContigiousSumFromZeroInARun += A[i];
if(MaxContigiousSumFromZero < MaxContigiousSumFromZeroInARun)
{
MaxContigiousSumFromZero = MaxContigiousSumFromZeroInARun;
FirstIndex = i;
}
}
else
break;
}
int MaxContigiousSumFromLast = 0, MaxContigiousSumFromLastInARun = A[n - 1];
for(int i = n - 2; i >= 0 && i > FirstIndex; i--)
{
if(MaxContigiousSumFromLastInARun + A[i] > A[i])
{
MaxContigiousSumFromLastInARun += A[i];
if(MaxContigiousSumFromLastInARun > MaxContigiousSumFromLast)
MaxContigiousSumFromLast = MaxContigiousSumFromLastInARun;
}
else
break;
}
if(MaxContigiousSumFromLast + MaxContigiousSumFromZero > MaxSumInRegularArray)
return MaxContigiousSumFromLast + MaxContigiousSumFromZero;
else
return MaxSumInRegularArray;

}</pre><pre title="CodeMonkey18054" input="yes">
</pre>

int MaximumContigiousSumInACircle(int *A, int *n)
{
int MaxSumInRegularArray = MaximumContigiousSum(A,n);
int MaxContigiousSumFromZeroInARun = A[0], MaxContigiousSumFromZero = 0, FirstIndex = 0;
for(int i = 1; i < n; i++)
{
if(MaxContigiousSumFromZeroInARun + A[i] > A[i])
{
MaxContigiousSumFromZeroInARun += A[i];
if(MaxContigiousSumFromZero < MaxContigiousSumFromZeroInARun)
{
MaxContigiousSumFromZero = MaxContigiousSumFromZeroInARun;
FirstIndex = i;
}
}
else
break;
}
int MaxContigiousSumFromLast = 0, MaxContigiousSumFromLastInARun = A[n - 1];
for(int i = n - 2; i >= 0 && i > FirstIndex; i--)
{
if(MaxContigiousSumFromLastInARun + A[i] > A[i])
{
MaxContigiousSumFromLastInARun += A[i];
if(MaxContigiousSumFromLastInARun > MaxContigiousSumFromLast)
MaxContigiousSumFromLast = MaxContigiousSumFromLastInARun;
}
else
break;
}
if(MaxContigiousSumFromLast + MaxContigiousSumFromZero > MaxSumInRegularArray)
return MaxContigiousSumFromLast + MaxContigiousSumFromZero;
else
return MaxSumInRegularArray;

}

package InterviewQ;

public class MaxContSumArc {

public static void maxArc(int[] arr) {
int max_so_far = 0;
int max_ending_here = 0;
int temp_end_idx = 0;
int temp_start_idx = 0;
int end_idx = 0;
int start_idx = 0;
for(int i=0; i<2*arr.length; i++) {
if(i-temp_start_idx < arr.length) {
max_ending_here += arr[i%arr.length];
if(max_ending_here < 0) {
max_ending_here = 0;
temp_start_idx = i+1;
temp_end_idx = i+1;
}
else {
temp_end_idx = i;
}
if(max_so_far < max_ending_here) {
start_idx = temp_start_idx % arr.length;
end_idx = temp_end_idx % arr.length;
max_so_far = max_ending_here;
}
}
else {
max_ending_here = 0;
i = temp_start_idx;
temp_end_idx = ++temp_start_idx;
}
}
System.out.println("start index: "+start_idx+" end index: "+end_idx+" sum: "+max_so_far);
}

public static void main(String[] args) {
int[] arr = {200, -10, -10, -10, -10, -10, 100};
MaxContSumArc.maxArc(arr);
}

}

Do let me know if this works.

1 #include <stdio.h>
  2 #include <stdlib.h>
  3 //arr == array
  4 //n == size
  5 //sum == max sum
  6 //l == lower bound
  7 //u == upper bound
  8 //circ == 1 for circular 0 otherwise
  9 int findmax(int* arr, int n, int* sum,int *l, int *u, int circ)
 10 {
 11         //Check if array size is correct
 12         if(n <= 0)
 13                 return 0;
 14         //Will hold temp max value. Could have just used *sum here
 15         int max_so_far = 0;
 16         //Ending of for loop
 17         int end;
 18         //if circular twice elements - 1
 19         //eg. 1 2 3 4 5 == 1 2 3 4 5 1 2 3 4
 20         if(circ)
 21                 end = 2*n-1;
 22         else
 23                 end = n;
 24         //j start of subarr
 25         int j = 0;
 26         //i loop counter
 27         int i = 0;
 28         //t temp sum
 29         int t = 0;
 30         for(i = 0; i < end; ++i)
 31         {
 32                 //If crosses boundary. Make arrangements for circular calculation.
 33                 if(i>=n && ((i - j) == n))
 34                 {
 35                         //Remove the last element.
 36                         t -= arr[j%n];
 37                         //Increment j
 38                         ++j;
 39                         //Check if elements are less that equal to 0 and hence not contributing towards max_sum.
 40                         //Remove these elements.
 41                         while((j < i) && (arr[j%n] <= 0))
 42                         {       t -=arr[j%n];
 43                                 ++j;
 44                         }
 45                         //If t has become less than 0 set it to zero.
 46                         //May not require this.
 47                         if(t<=0)
 48                         {
 49                                 t = 0;
 50                         }
 51                 }
 52                 //Normal Kanade's max_sum algo. 
 53                 t = t + arr[i%n];
 54 
 55                 if(t > max_so_far)
 56                 {
 57                         *u = i%n;
 58                         *l = j%n;
 59                         max_so_far = t;
 60                 }
 61 
 62                 if(t<=0)
 63                 {
 64                         j = i;
 65                         t = 0;
 66                 }
 67         }
 68         *sum = max_so_far;
 69         return 1;
 70 
 71 }
 72 
 73 
 74 int main()
 75 {
 76         int* arr;
 77         int n = 0;
 78         //Input size of array
 79         scanf("%d",&n);
 80         arr = (int *)malloc(n*sizeof(int));
 81         if(!arr)
 82                 return 1;
 83         int i = 0;
 84         int l = 0;
 85         int u = 0;
 86         int sum = 0;
 87         //read array elements
 88         for(i = 0;i<n;++i)
 89         {
 90                 scanf("%d",&arr[i]);
 91         }
 92         int circ;
 93         //check if circular array or not
 94         scanf("%d",&circ);
 95         //call function to find sum
 96         //l == lower bound
 97         //u == upper bound
 98         if(!findmax(arr,n,&sum,&l,&u,circ))
 99                 return 2;
100         printf("Sum: %d\n",sum);
101         free(arr);

(1) Put the elements in an array.
(2) Divide array into two parts. Let it be A and B.
(3) Let ASum be max sum in A and BSum be max sum in B.
(4) Let AlSum be array sum left to ASum array and ArSum be array sum right to th
e ASum array. Similarly are BlSum and BrSum.
(5)

maxSum = ASum;
if( BSum > maxSum )
maxSum = BSum;
if(ASum + AlSum + BrSum + BSum > maxSum)
maxSum = AlSum + ASum + BrSum + BSum;
if(ASum + ArSum + BlSum + BSum > maxSum)
maxSum = ASum + ArSum + BlSum + BSum > maxSum;

print maxSum

(1) Put the elements in an array.
(2) Divide array into two parts. Let it be A and B.
(3) Let ASum be max sum in A and BSum be max sum in B.
(4) Let AlSum be array sum left to ASum array and ArSum be array sum right to th
e ASum array. Similarly are BlSum and BrSum.
(5)

maxSum = ASum;
if( BSum > maxSum )
maxSum = BSum;
if(ASum + AlSum + BrSum + BSum > maxSum)
maxSum = AlSum + ASum + BrSum + BSum;
if(ASum + ArSum + BlSum + BSum > maxSum)
maxSum = ASum + ArSum + BlSum + BSum > maxSum;

print maxSum

There has to be at least one negative number in the sequence. What if all the elements are positive ? will the solution be infinity ??

<pre lang="" line="1" title="CodeMonkey96656" class="run-this">int getMaxSumofSubArr(int *arr, int nLength)
{
if (NULL == arr)
MYASSERT(0);

int maxsubsum = arr[0];
int premax = arr[0];
int index = 0;
int begin = 0;
for (int i = 1;i < 2*nLength;i++)
{
index = i%nLength;
if (index == begin)
break;
premax += arr[index];
if (premax < arr[index])
{
premax = arr[index];
begin = index;
}
maxsubsum = max(maxsubsum,premax);
}
return maxsubsum;
}</pre><pre title="CodeMonkey96656" input="yes">
</pre>

#include<stdio.h>
#include<iostream>

using namespace std;

int main()
{
	int n ; 
	int i ; 
	int a[100] ;
	int use[100] ;
	int maxsum  ;
	int length  ; 
	int prev ; 
	int curr ;
	int sum1 ; 

	cin >> n ; 
	for(i = 0 ; i < n ; i++)
	{
		cin >> a[i] ; 
		use[i] = a[i] ; 
	}

	for(i = 0 ; i < n ; i++)
	{
		use[n + i] = a[i] ; 
	}

	
	maxsum = 0 ;
	prev = 0 ; 
	curr = 0 ;
	sum1 = 0 ; 
	length = 0 ; 
	
	while(1)
	{
		if(curr >= 2*n)
			break ; 
		if(use[curr] + sum1 >= maxsum)
		{
			maxsum = use[curr] + sum1 ;
			sum1 = use[curr] + sum1 ; 
//			cout << maxsum << " " << use[curr] << " " << sum1 << endl;
			length ++  ;
			curr ++ ; 
			if(length == n)
			{
				sum1 -= use[prev];
				prev ++ ;
				length -- ; 
			}
		}
		else if(use[curr] + sum1 < 0)
		{
			sum1 = 0 ; 
			length = 0 ;
			prev = curr + 1 ;
			curr ++ ;
		}
		else if(use[curr] + sum1 < maxsum)
		{
			sum1 = use[curr] + sum1 ; 
			curr ++ ;
			if(length == n)
			{
				sum1 -= use[prev] ; 
				prev ++ ;
				length -- ; 
			}
		}
	}
	
	printf("%d\n",maxsum);

	return 0;
}