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:

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

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

We love you <333333. Your videos are so helpful!

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

Brilliant

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?

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

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

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.

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

Is this channel working or gone?

17:21 , code has a bug if array[0] = negative.

thanks a lot mann!! finally

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

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.

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.

Thanks a lot

"pawcitive"

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 ?

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

Loved it. ❤️

Thanks bro 🙂

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)

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[0]);

g_max=c_max=arr[0];

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;

}

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])

helpful video, thank you

finally I understand Kadane's algorithm, thanks

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

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?

Which book do u recommend for DSA? thank you.

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!