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

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” To 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]]

``` Complete Code:

Output:

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

__________________________________________________
Top Companies Interview Questions..-

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

### 15 Responses

1. eugen_nw says:

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 says:

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

• Eugen Daroczy says:

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

• tutorialhorizon says:

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

2. Badalov Turkhan says:

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

• Murad Talibov says:

Sehvtutan olmusan e??? 😀

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

• Badalov Turkhan says:

Sehv tutan olmusan, e? 😀

• Badalov Turkhan says:

Ayəə, haraya gessən)))

3. ahmedaebaid says:

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;
}

4. lipsa patel says:

you can have it this way

solution = array;

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

5. Oliver Liu says:

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 says:

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 🙂

6. swadhin goswami says:

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.

7. Jay says:

Here is the easy solution

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

solution = nums;
int max = solution;

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

8. GeorgeNav says:

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

}

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