Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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.


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.


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” 

Maximum Subarray ProblemTo 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]]

Recursive Equation- Maximum Subarray Problem

Com­plete Code:


[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);

    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.

  • Badalov Turkhan

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

    • Murad Tal­i­bov

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

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

      • Badalov Turkhan

        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;