Adobe Interview Question Developer Program Engineers
Kadane's with modification. Original Kadane's doesnt work for an array having negative numbers only.
@Tulley: seems your code has bugs in the logic. Check out with below input, for which output is expect 10 (your code shows 9).
int a[] = { 5, -2, -4, 3, 7 }
Here's my code to get the max value. Pls try to catch flaw in it. Thanks.
ASSUMPTION: input has atleast 1 element
void maxSum2 (int *a, int n)
{
int result = a[0];
int curSum = a[0];
for(int i=1; i < n; i++ )
{
if ( curSum > 0 ) curSum += a[i] ;
else curSum = a[i] ;
if ( curSum > result ) result = curSum;
}
printf("MaxSum :%d\n", result);
}
@Anon: Thanks for pointing out the mistake. I am not able to find any mistake in your code :)
I was more concern about printing the start and end index of the array. I have corrected the my prev code now.
@anon
Check your solution for this input:
-6 4 20 -15 -10 15
Your code outputs 15 but the correct answer is 24. :)
@ Anon : For this set of 7 numbers , your code will give incorrect output
-1,2,3,4,-5,1,10
It will give output as 15 instead of 11 .
How smart are you to claim that 15 is less than 11 :-O
Hope you are not drunk........lol
Its a DP solution of O(n).
SUM=MAX{CURRENT SUM + A[i], A[i]} where 1<=i<=N
- Tulley March 27, 2011void maxSum (int* pArray, int size) { int sum=pArray[0], curSum=pArray[0], startInd=0, endInd=0, index=0; for(index=1; index<size; index++) { if((curSum + pArray[index])> pArray[index]) { curSum = curSum + pArray[index]; } else { curSum = pArray[index]; if(sum<0) { startInd = endInd; } else { startInd=index; } } if(sum<=curSum) { sum=curSum; endInd = index; } } printf("[Start Index]:%d\n[End Index ]:%d\n", startInd, endInd); printf("[MaxSum ]:%d\n", sum); }