Dynamic Programming – Maximum Subarray Problem

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.


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.


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-1th 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:


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

15 thoughts on “Dynamic Programming – Maximum Subarray Problem”

  1. 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);

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

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

  3. 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]);

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

    • 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 🙂

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

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

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



Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.