Amazon Interview Question
Country: India
Interview Type: In-Person
If I am reading the circle twice than I can very well do it naively... I think the interviewer wants an O(n) time and O(1) space complexity solution
The above soln. is O(n) only in time complexity , although the space complexity is O(n)!
A naive approach to this problem is to take each element from the circle and calculate the maximum sum that can be obtained from that point.
It's like running the algorithm of "maximum sum sub array problem" for each array obtained by traversing the circle from every element of the circle, but instead of continuing when the sum is less than 0, you just move to the next array.
At the end get the maximum no. of these maximums.
For e.g, for circle [200 -10 -10 -10 -10 -10 100],
1. first, you will find the subarray which starts with 200 and have the sum of elements maximum; this translates in running the
"maximum sum sub array" algorithm on [200 -10 -10 -10 -10 -10 100]; this will return 250
2. then, you will find the subarray which starts with -10 and have the sum of elements maximum; this translates in running the
"maximum sum sub array" algorithm on [-10 -10 -10 -10 -10 100 200]
calculate the maximum sum that can be obtained; if the starting point is negative then ignore this step and go to next element in the circle
... and so forth
n. till the last element 100, where you will find the subarray which starts with 100 and have the sum of elements maximum; this translates in running the "maximum sum sub array" algorithm on [100 200 -10 -10 -10 -10 -10]; this will return 300
The time complexity will be like O(n*n)
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.
ishant,
you are correct . thia problem can be resolved in single pass i.e. in o(n) complexity . Its a variation of maximum sub array sum problem .
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
<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>
This returns the sum, the question asks to return the sub-array that is the maximum (the arc)
#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;
}
We can change the problem to this: give you 2*n numbers, query you that the maximum sum of less than n contiguous number.
- hzshuai September 27, 2011Then 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