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.

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” 

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:

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.

  • 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])