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:

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

37 COMMENTS

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

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

  3. 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.

  4. 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.

  5. 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.

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

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

  8. 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)

  9. 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;

    }

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

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

  12. 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.

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

  14. 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

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

LEAVE A REPLY

Please enter your comment!
Please enter your name here