# Maximum sum sub-array

On this lesson, we now have solved one other well-known programming interview query – discovering most sub-array sum in an array.

See supply codes right here:

O(n^3) algorithm – https://gist.github.com/mycodeschool/9666221e7527935d8e1d

O(n^2) algorithm –

https://gist.github.com/mycodeschool/447854ea1844b1b42cd3

O(NlogN) algorithm –

https://gist.github.com/mycodeschool/8b4bcff69427c8a6f2aa

O(N) algorithm –

https://gist.github.com/mycodeschool/4b0b01e1d08932066301

See playlist on programming interview questions right here:

https://www.youtube.com/playlist?checklist=PL2_aWCzGMAwLPEZrZIcNEq9ukGWPfLT4A

See collection on time complexity right here:

https://www.youtube.com/watch?v=V42FBiohc6c&checklist=PL2_aWCzGMAwI9HK8YPVBjElbLbI3ufctn&index=2

Evaluation of quicksort:

https://www.youtube.com/watch?v=3Bbm3Prd5Fo

You may additionally like/observe us on Fb/Twitter:

https://www.fb.com/MyCodeSchool

Tweets by mycodeschool

Video creator : Ashwin Krish – intern at MyCodeSchool

source

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.

Awesome bro.Very good explanation

helpful tutorial sir, thank you 👍👍🙂🙂

Excellent.

First of all clear your basics.

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

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

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

second approach has a bug!

Divide and Conquer approach is not explained good. Lots of confusion after listening that part. Rest explanations are good.

thanks

Its so funny when u say 'sabarrei' (subarray) . Nice video!

Brother come up with more of it….come on…..you are awesome

at 10:14

how 5+3=6 ????????????????????????????????

I lost interest at 2:25 when INT_MIN was introduced. A language construct was not necessary to explain any Algo. It will just make a user check another resources. Once they check there is a chance may stick to them. Be careful with internships.

Please remove this video. Highly confusing and seems the instructor is just writing down mugged code. There is no talk about logic why something is done in given manner like why Kadane algo resets value to zero.

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.

Good work, thanks!

However, I think divide and conquer should take 3 arguments:

int Max_Subarray_Sum(int arr[], int low, int high)

where n corresponds to (high+low)/2

nice Video!

what if a certain distance between the individual elements had to be complied with, eg. at least 2 distance. How could you calculate the sum? Any ideas? I would appreciate it very much.

Nice solution. if subarray is having less than 0 value there is no use adding a +ve or -ve value instead assigning the same to it.liked this thought!!

In the divide and conquer approach code:

the replacement of the line 'for(int i=m-1;i>=0;i–)' with 'for(int i=0;i<m;i++)' for finding left sum doesn't work. Why??

Divide and Conquer approach doesn't work with input array [3,-2,-4,7]

Thanks for your help! Much easier than just trying to understand the solution on my own!

Fantastic video!! I don't get the negativity on the comments. I had to pause a couple of times yes but it is a complex issue. Kadane solution was beautiful.

does this algorithm support an array with all negative values

i really understood his explanations after running his code line by line in pythontutor.com. the way these things work is mind-blowing to me lol. these videos are amazing

Awesome explanation. Very well followed.

+Ashwin Krish nice explanation , all the other videos directly explain the algo, you explained why it works thank you

what if I need the starting index and ending index of the subarray? using divide and conquer

10:17 is this O(N log N) or O(n)?

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?

if you have negatives then it does not work

What software did you use to write in this video? Looks very clean

Hey,You Could also write the Segment Tree Solution because we may face masochistic time constraints sometime in future.

Which software you use for editing the videos?

omg thank you very much for this video. it saved me tons of hours. Cheers!