Amazon Questions / Arrays / Bloomberg / Difficulty Level / Dynamic Programming / Intermediate / Software Development Engineer (SDE) / Software Engineer / Top Companies / Uncategorized
14

Dynamic Programming – Maximum Subarray Problem

by SJ · April 3, 2016

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-1“^th 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

Tags: Intermediate

eugen_nw

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
  
  Thanks eugen, I have corrected the post. Do let me know if you find some other issues in other posts.
  - Eugen Daroczy
    
    You’re welcome. Very good site, thanks very much for creating and maintaining it!
    - tutorialhorizon
      
      Thanks . your words are encouraging. Will try to live up to expectations.
Badalov Turkhan

There is syntax mistake at 11th line: a[j-1) should be a[j-1]
- Murad Talibov
  
  Sehvtutan olmusan e??? 😀
  
  Nope, a[j-1) should be a[j-1])
  - Badalov Turkhan
    
    Sehv tutan olmusan, e? 😀
  - Badalov Turkhan
    
    Ayəə, haraya gessən)))
ahmedaebaid

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

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]);
}
Oliver Liu

I don’t see how this make sense. You said

“To calculate the solution for any element at index “i” has two options

EITHER added to the solution 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
  
  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 🙂
swadhin goswami

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

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;

Dynamic Programming – Maximum Subarray Problem

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

Related Posts:

Like this:

Select level