Programming Interview 16: Find Largest subsequent sum in array in O(N) time

Step by step to crack Programming Interview questions 16: Find the maximum sum of a consecutive subset in an array in O(N) time

Example:
(-1, 2, 3, 5, -2) Max subset sum is 8 for the subset (3,5)

Solution:
1. Proceed number by number
2. Keep track of temporary sum of all numbers processed so far
2.1. If (tempSum is larger than 0)
The temp sum so far can be part of the result max-sum subset
2.2. Else,
This temp sum will not be part of result max-sum subset
reset the tempSum to 0 and proceed
3. Keep track of the max tempSum and return as result

[lubenalexandrov]

Great channel man! You are really helping a lot of people with your videos!
For this question:
As already pointed your code won't work for arrays with only negative values, it will return 0 in such cases. There are also other problems with the code. This should be a correct solution: 


public static int findMaxSum(int a[]) {
if (a.length == 1)
return a[0];
int maxSum = a[0];
int currentMaxSum = maxSum;
for (int i = 1; i < a.length; i++) {
if (a[i] >= 0) {
currentMaxSum += a[i];
} else {
//a[i]<0
maxSum = Math.max(maxSum, currentMaxSum);
if(i+1 < a.length) {
(a[i+1] >= 0)
= 0;

= a[i];
}
}
}
return Math.max(maxSum, currentMaxSum);
}

[AI_Edu_]

I agree the difference relies on if selecting no elements is allowed or not. Of course your fixing solution will be a good addition! ^_^ Thanks~

[AI_Edu_]

Cool! I didn't know the method has a formal name. Thanks for sharing.

[abkyabacha]

I solved this problem long back...later on I found out that same solution already exists and is known as Kadane's algo...:D

[wy]

I agree with anfielddir, there is a problem with the code. The intention of the code is to return the maximum subsequence. If all numbers are negative it should return the maximum negative number. If you return 0, for an array containing all negative numbers that's just wrong given the code's stated intent.

[chandlerbing]

this is a maximum sub array problem and we can solve it using divide and conquer ..It's solution is given in Cormen(CLRS is the most efficient way to solve this problem

[mintoocool]

(-1, 2, 3, 5, -2) Max subset sum is 8 for the subset (3, 5) ?

Why ?

Why not 10 => {2, 3, 5} ?

[indianboine]

this video helped allot thank you so much.

[AI_Edu_]

Thanks. But there is no bug in my code. If you try all negative values, it returns zero which means select no element at all. That's the default setting (maxSum=0).

[titombo]

{ -1, -2, -3, -5, -2 } => -1, but it is returning 0. The description should be:

Find the maximum NON-NEGATIVE sum of a consecutive subset in an array in O(N) time

[sameerdoha]

Your description has an error. Probably a typo. I think you meant (-1, -2, 3, 5, -2) for input. You missed the negative sign at the first "2". Your algorithm is fine!

[erdogany]

I think he meant the description of video. It mentions; { 3, 5 }

[anfieldir]

Yeah, but shouldn't it return the largest negative value (smallest negative number)? For example: -7 -3 -2 -1 -5 -6. The "maximum sum of a consecutive subset" is -1, not 0 (and you should not return "no element" as that case is valid). Fixing it would be easy and efficient though, if maxSum still remained 0 all the way to the end (= no positive values, an extremely rare but valid case in large arrays), return the smallest negative number. It would still be O(N).

[huideyin]

in your solution, you wrote so, it also confused me for a long time.

[uditmanit]

If all no's are -ve, the output should be the min -ve no. this solution will return 0

[manchonu]

What would happen if all the elements in the array are negative?

[AI_Edu_]

Not sure what happened to you but my code successfully returns 10 using your test case. Try download my code and see if you have the correct output.

[NitishUpreti]

This does not give us a contiguous subarray right?

[kevin]

I don't think this is right. It should return [2, 3, 5]

[yevgenitarler]

he talks about the vid itself.
check 00:08