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
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]);
Thanks eugen, I have corrected the post. Do let me know if you find some other issues in other posts.
You’re welcome. Very good site, thanks very much for creating and maintaining it!
Thanks . your words are encouraging. Will try to live up to expectations.
There is syntax mistake at 11th line: a[j-1) should be a[j-1]
Sehvtutan olmusan e??? 😀
Nope, a[j-1) should be a[j-1])
Sehv tutan olmusan, e? 😀
Ayəə, haraya gessən)))
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;
}
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]);
}
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.
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 🙂
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.
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;
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];
}