# Dynamic Programming — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum.

Exam­ple:

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:

Ear­lier we have seen how to solve this prob­lem using Kadane’s Algo­rithm. In this post we will how to solve it using Dynamic pro­gram­ming.

We will solve this prob­lem in bottom-up manner.

let’s say

MS(i)  is max­i­mum sum end­ing at index i”

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-1th index
• OR start a new sum from the index “i”.

Recur­sive Solution:

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

Com­plete Code:

Out­put:

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

#### You may also like...

• eugen_nw

If all inte­gers in the array are neg­a­tive, this algo­rithm will return the incor­rect result of 0. In that sce­nario the max­i­mum sub­ar­ray will have a length of 1 and will con­tain only the largest neg­a­tive num­ber. To address this issue the for­mula 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]);

• tuto­ri­al­hori­zon

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

• Eugen Daroczy

You’re wel­come. Very good site, thanks very much for cre­at­ing and main­tain­ing it!

• tuto­ri­al­hori­zon

Thanks . your words are encour­ag­ing. Will try to live up to expectations.

There is syn­tax mis­take at 11th line: a[j-1) should be a[j-1]

Sehv­tu­tan olmu­san e??? 😀

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

Sehv tutan olmu­san, e? 😀

• ahmedae­baid

Thanks for shar­ing the solu­tion. In my opin­ion, you can improve on the given solu­tion by using only two extra vari­ables to avoid a O(n) space complexity.

pub­lic sta­tic int maximumSubarray(List list) {
int max­So­Far = Integer.MIN_VALUE, maxNow = 0;
for (Inte­ger i : list) {
maxNow += i;
if (max­So­Far < maxNow) {
max­So­Far = maxNow;
}
if (maxNow < 0) {
maxNow = 0;
}
}
return max­So­Far;
}