Maximum sum sub-array

In this lesson, we have solved another famous programming interview question - finding maximum sub-array sum in an array.

See source codes here:
O(n^2) algorithm -
O(NlogN) algorithm -
O(N) algorithm -

See playlist on programming interview questions here:

See series on time complexity here:

Analysis of quicksort:

You may also like/follow us on Facebook/Twitter:

Video creator : Ashwin Krish - intern at MyCodeSchool

[GurdeepSabarwal]

1:20(n^3, Brute Force), 5:02(n^2, Brute Force), 7:10(nlogn -D&C), 12:56( n-kadnae)

[HarshitKumar-bxpt]

7 years have passed but still, this channel remains the best for understanding any algorithm.

[mahesh_jamdade]

for Kadane;s algorithm with negative numbers You can use the existing code in this video and maintain a boolean variable to check if list contains atleast 1 negative number.
```
containsOnlyNegative = True
for(..i < n..){
if(sum + arr[i] > 0){
containsOnlyNegative = False
....
}
}
if(containsOnlyNegative)
return max(Array)
else
return ans
```
And at the end if(containsNegative) return max(array)

[sohambhattacharya]

For those whose wondering how we get 6 in the recursive solution let me explain.
its correct, he is actually finding the max sum of the left and right sub arrays. For the left part (3, -2) max sum is 1(starting from left) and for the right part(5, -1) is 5(starting from the left), since we are finding the value of the overlapped sub-string. 5+1>3, 5 hence the sum of max sub array is 6
Carefully watch 7:45 to 9:08, repeat over until you understand.
Kandane's Algorithm is just plain wrong.

[allfreetechhub]

Thanks for the great video buddy.
:)
It helped a lot. Though it has a little problem. The second approach (the one with O(n^2) time complexity) uses one redundant step. When it checks for "subarray exceeds array bound". That check can be simply put inside the for loop itself in place of an extra if check. Otherwise, practically the same thing is being checked twice(once in for loop, and once in the if condition)

Modified code is as below :

(Notice the check in the second for loop)

int max_sub_array(int * array, int n, int * start, int * end)
{

        int start_index, sub_array_size, k, sum, max_sum = 0;
        max_sum = INT_MIN;

        for (start_index = 0; start_index < n; i++)
        {
                sum = 0;
                for (sub_array_size = 1; start_index + sub_array_size <=n; sub_array_size++)
                {
                        sum += array[start_index + sub_array_size - 1];                 //      Last element of new subarray

                        if (sum > max_sum)
                        {
                                max_sum = sum;
                                *start = start_index;     *end = start_index + sub_array_size;
                        }
                }


        }
        return max_sum;

}

[whoispankaj]

And if somebody doesn't know this Kadane's algorithm, how is he supposed to solve this in an interview of 30 mins which Kadane would have taken years to solve?

[chloekimball]

Nicely explained. Extremely well written code. Clean and easy to understand unlike some over-complicated garbage that you find on the internet.

[nitinmendiratta]

I am a true follower of mycodeschool but I honestly didn't liked this video much, as usually in all the other videos of Animesh sir he tracks the code taking an example but that explanation was missing in this video. Please if you could implement the approach followed by Animesh from now that would be great.

[abhishekbhadoriya]

I think I have encountered the first ever mycodeschool video which I did know understand !!

[ian_senior]

i voted down because @ 10:18 you have left MSS = 3 and right MSS = 5 which is fine, but then magically with no explanation the left sum + right sum is 6. 5 + 3 = 8, you need to explain how you arrive at 6. visually i can see it is the 3 + -2 + 5, but your process doesn't explain how the code will know to add just those 3 numbers to arrive at the combined sum.

[shikharbhatia]

Nice explanation...However, i would like to point out a mistake in the O(n) program provided in the github link.
" int ans = A[0], sum = 0; " is there. However, it should be replaced as:
" int ans = arr[0], sum = 0;" because array A[0] is not declared anywhere.
Thanks!

[owusuosei]

By modifying Kadane's algorithm slightly (initializing maxSum to the MIN_VAL) you can remove the limitation of expecting the existence of a positive value. You'll have to rearrange the logic slightly. Find Java code below.


public int maxSubArray(final List<Integer> A) {
if (A.size() == 0) return 0;

int maxSum = Integer.MIN_VALUE;
int runningMaxSum = 0;

for (int i = 0; i < A.size(); i++){
runningMaxSum += A.get(i);
maxSum = Math.max(maxSum, runningMaxSum);

if (runningMaxSum < 0) runningMaxSum = 0; // reset if sum becomes negative
}

return maxSum;
}

[ahmedbrown]

The version of Kadane's Algorithm shown on Wikipedia works regardless of whether the array contains all negative numbers or not.

[ultiumlabs]

finally I understand Kadane's algorithm, thanks

[mycodeschool]

This video has been created by - an intern at MyCodeSchool

[MrMynameisanthonygon]

Wtf is wrong with all the negative comments? This video is very good. Please apply some of your own minds also rather than leaving everything on the tutor.

[jlpeng]

10:14 left_MSS =3 ; right_MSS = 5; But Left_sum + right_sum, would it be 1 + 4??? = 5, since you are talking about right_SUM?

[sandeeprajakrishnan]

it gives me chills that the speaker is no more, rip

[tikaramsanyashi]

Really a nice video. It helped me to understand the maximum sum sub-array well. Thanks.

[GautamSingh-yncb]

@8:46 please explain why we need to go from right to left in left subarray when we have both indices available, lower and mid.