Dynamic Programming – Maximum Subarray Problem

by · April 3, 2016

Objective:  The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Example:

int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4};

Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Approach:

Earlier we have seen how to solve this problem using Kadane’s Algorithm. In this post we will how to solve it using Dynamic programming.

We will solve this problem in bottom-up manner.

let’s say

“MS(i)  is maximum sum ending at index i” 

Maximum Subarray ProblemTo calculate the solution for any element at index “i” has two options

  • EITHER added to the solution found till “i-1“th index
  • OR start a new sum from the index “i“.

Recursive Solution:

MS(i) = Max[MS(i-1) + A[i] , A[i]]

Recursive Equation- Maximum Subarray Problem

Complete Code:



Output:

[0, 1, 3, 0, 0, 2, 9, 7, 10]
Maximum subarray is  10

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Tags:

  • eugen_nw

    If all integers in the array are negative, this algorithm will return the incorrect result of 0. In that scenario the maximum subarray will have a length of 1 and will contain only the largest negative number. To address this issue the formula on line #11 needs to change from:
    solution[j] = Math.max(solution[j-1]+a[j-1], 0);

    into:
    solution[j] = Math.max(solution[j-1]+a[j-1], a[j-1]);

    • tutorialhorizon

      Thanks eugen, I have corrected the post. Do let me know if you find some other issues in other posts.

      • Eugen Daroczy

        You’re welcome. Very good site, thanks very much for creating and maintaining it!

        • tutorialhorizon

          Thanks . your words are encouraging. Will try to live up to expectations.

  • Badalov Turkhan

    There is syntax mistake at 11th line: a[j-1) should be a[j-1]

    • Murad Talibov

      Sehvtutan olmusan e??? 😀

      Nope, a[j-1) should be a[j-1])

      • Badalov Turkhan

        Sehv tutan olmusan, e? 😀

      • Badalov Turkhan

        Ayəə, haraya gessən)))

  • ahmedaebaid

    Thanks for sharing the solution. In my opinion, you can improve on the given solution by using only two extra variables to avoid a O(n) space complexity.

    public static int maximumSubarray(List list) {
    int maxSoFar = Integer.MIN_VALUE, maxNow = 0;
    for (Integer i : list) {
    maxNow += i;
    if (maxSoFar < maxNow) {
    maxSoFar = maxNow;
    }
    if (maxNow < 0) {
    maxNow = 0;
    }
    }
    return maxSoFar;
    }

  • lipsa patel

    you can have it this way

    solution[0] = array[0];

    for (int i = 1; i < array.length; i++) {
    solution[i] = Math.max(solution[i-1] + array[i], array[i]);
    }

  • Oliver Liu

    I don’t see how this make sense. You said

    “To cal­cu­late the solu­tion for any ele­ment at index “i” has two options

    EITHER added to the solu­tion found till “i-1“th index
    OR start a new sum from the index “i”.”

    This is clearly not true. There’s a third option: Stick with the solution at index i-1 and do not add element of index i to it. The logic fails apart.

    • Alex Charrier

      Hello,
      The subarray must be contiguous so either you add the element of index i, or you start a new sum.
      Otherwise the problem is more complicated 🙂

  • swadhin goswami

    I think for loop range for below code should be “j <=solution.length" instead of "j <solution.length"

    for (int j = 1; j <solution.length ; j++) {

    For ex: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; result will be 4, −1, 2, 1, with sum 6.
    But for this case, int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 14}; result ll return 6 instead of 14. because we are not checking with last index.
    Here we this modification with loop range.

  • Jay

    Here is the easy solution

    int solution[] = new int[nums.length];

    solution[0] = nums[0];
    int max = solution[0];

    for (int i = 1; i max) {
    max = solution[i];
    }
    }
    return max;

  • GeorgeNav

    So you don’t have to iterate throughout the whole solution array again I would suggest to put the if statement in the first for loop

    for (int i = 1; i < (n+1); i++) {

    solution[i] = Max(solution[i-1]+S[i-1],S[i-1]);

    if(result < solution[i])

    result = solution[i];

    }

Follow:

Select level

Beginner
Intermediate
Expert

Follow me on Twitter

%d bloggers like this: