# Maximum sum sub-array

37
3 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^3) algorithm –
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:

Video creator : Ashwin Krish – intern at MyCodeSchool

Nguồn: https://freecode.com.vn

Xem thêm bài viết khác: https://freecode.com.vn/mobile

1. Apoorva Singh

2. Tanay Chauli

Watched this approach https://youtu.be/34ZeLxbkMw8

3. Hrishikesh Shinde

Brilliant

4. Nicolas Soto

If you’re a 4th year CS student about to graduate and needed to look this problem up because you were stuck on it, is this the end for me?

5. parth gupta

what if theres no assurance that it has atleat one positive integer?

6. Ramu Mandaloju

You can even use Dynamic Programming in-order to get it in O(n) , however, it costs O(n) space complexity

7. Shubham Sharma

I have been following my code school for last 6 years. This is the only pathetic lesson.
Certainly not a logical explanation and certain parts which are important missing.

8. Aman Chouhan

it fails input [-2,-1] at leetcode

9. Kshitiz Pathak

Is this channel working or gone?

10. 17:21 , code has a bug if array = negative.

11. thanks a lot mann!! finally

12. Dawid Ciężadlik

This is a brilliant last solution. Thank, thanks, thanks.

13. Mrinal Sharma

the output is wrong for an array consisting of all negative elements.
the answer should by the greatest number negative number among them but your solution is printing zero.
kindly look onto it.

14. abishek kachroo

At 11.20
right_Mss = MAx_SubArray_Sum(arr+m, n-m);
How is this possible
arr is the array and m is the int , how can this be added
If somebody can please explain this to me.

15. Jaya Pandey

Thanks a lot

16. Mihir Trivedi

"pawcitive"

17. girish singh

What if i add an positive element '1' in array hence there will be a positive value can i then apply kadane's algo alwayas (i know it will increase size of array amd we can cal always subtract what we added in array from sum ,adding element in last in constant anaway) will this work ?

18. Zeeshan Ashraf

The statement : 'variable sum tries to calculate the MSS at index i' is incorrect. Actually variable ans has the MSS at index i.

19. Meet Palod

Loved it. ❤️

20. Julio Abraham Garcia

Thanks bro 🙂

21. Beatriz Oliveira

The solutions are a bit inconsistent with what you explained in the beginning. When there are only negatives should i return -1 or 0,? When it's said that -1 is the MSS, seems like we should return it, instead of 0 (max sum of empty subarray i suppose)

22. akshat singh

Easiest and most simple algorithm is
#include <iostream.h>

#include<conio.h>

/// Max Sum SubArray (Kadane's Algorithm) //

void main()

{

int arr[]={1,-3,2,-5,7,6,-1,-4,11,-23};

int g_max,c_max;

int ar_size = sizeof(arr)/sizeof(arr);

g_max=c_max=arr;

for(int i=1;i<ar_size;i++)

{

if(arr[i] < g_max + arr[i])

g_max = g_max + arr[i];

if(arr[i] > g_max + arr[i])

g_max = arr[i];

if(g_max > c_max)

c_max = g_max;

}

cout<<endl<<c_max;

}

23. XIAOHE DONG

This is incorrect. What happen for [-1] ? the result would return 0, but it should return -1.
By using Kadane algorithm, you can use _sum = max(nums[i], _sum + nums[i]) rather than _sum = max(0, _sum + nums[i])

24. Pushpendra Kumar

25. ultium labs

finally I understand Kadane's algorithm, thanks

26. Gurdeep Sabarwal

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

27. 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?

28. Bhavya Arora

Which book do u recommend for DSA? thank you.

29. Soham Bhattacharya

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.

30. Shubham Kumar

Awesome bro.Very good explanation

31. Smart Programming

helpful tutorial sir, thank you 👍👍🙂🙂

32. Ilyass Taouil

Excellent.

33. purusottam 2011

First of all clear your basics.

34. Chloe Kimball

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

35. ahmed ali

i have problem and i need to solve it
and i don't know how the solve the problem
if i input number such like 26712
the summation and subtract of the digit of this number is equal to zeros
and the output sholud be like that (- + – -) the output is
The addition and subtraction signals that I needed to get the output zero
if the output is not equale to zero then we print error

36. Ahmed Brown

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

37. Rahul Bhatia

second approach has a bug!