## Maximum Value Contiguous Subsequence (Maximum Contiguous Sum)

This is one of the first examples of Dynamic Programming that I’ll take up on this blog. It is a very famous problem with multiple variations. The reader should note that in problems involving DP, the concept is much more important than the actual problem. You should have a crystal clear understanding of the logic used so that you can use it in other problems which might be similar.

As we talked earlier in my (overview of Dynamic Programming), we need to find an optimal substructure (which is basically recursive in nature) in the problem so as to apply an iterative solution to the problem. For this particular problem, we’ll keep building the solution as we traverse the array (which complies with our thinking of solving simpler sub-problems to solve the bigger complex ones).

*Problem Statement**: *You are given an array with integers (positive, negative, zero) and you are supposed to find the maximum contiguous sum in this array. Hence, you have to find a sub-array which results in the largest sum.

Example, If the given array is,

5, -6, 7, 12, -3, 0, -11, -6

The answer would be, 19 (from the sub-array {7,12} )

If you go on to form all the possible sets and then finding the one with the biggest sum, your algorithm would have a mammoth-like time complexity. More importantly, you would be called a fool. 😛 So we use dynamic programming and finish this in time O(n) and people will think we are smart. 😉

Assume your input array is called A. What you need to do is form another array, say B, whose each value ‘i’ is calculated by using the recursive formula,

Maximum(A[i], B[i-1]+A[i])

What you are doing effectively is that you are choosing whether to extend the earlier window or start a new one. You can do this since you are only supposed to select continuous elements as part of your subsets.

The way B looks for the example I took earlier, is,

5, -1, 7, 19, 16, 16, 5, -1

So all you need to do now is traverse the array B and find the largest sum (since B has the optimized sums over various windows/subsets).

That should be easy to understand. If not, refer to video tutorial at:

*http://people.csail.mit.edu/bdean/6.046/dp/*

** Task for you : **Find the elements that form this maximum contiguous sum. Pretty easy. 🙂

Maximum(A[i], A[i-1]+A[i]) should be

B[i] = Maximum(A[i], B[i-1]+A[i])

The formula Maximum(A[i], A[i-1]+A[i]) is incorrect. The recursive formula should be Maximum(A[i], B[i-1]+A[i]).

True. I explained it properly but made an error in writing the formula. Corrected that. Thanks!

” Example, If the given array is,

5, -6, 7, 12, -3, 0, -11, -6

(…)

What you need to do is form another array, say B, whose each value ‘i’ is calculated by using the recursive formula,

Maximum(A[i], A[i-1]+A[i])

(…)

The way B looks for the example I took earlier, is,

5, -1, 7, 19, 16, 16, 5, -1″

from 19 onwards I fail to see how this happens…

Written A[I-1] instead of B[I-1]. My bad.

How about -1,-1,2,-1,10,-1

answer is 11 {2,-1,10}

Very explained. Much better than the video. I watched it first.

We can even do away with the B array, to make it inplace.(Kadane’s algorithm) Just keep track of the max sum discovered till now in some variable maxSoFar if the currentSum is greater than the maxSoFar, update that.

maxSoFar=currentSum=0;

for(i =0 to size){

currentSum+=a[i];

if(currentSummaxSoFar

}

maxSoFar will contain the final ans. This will fail in all -ve array, but in that case, one more traversal can be done to return the greatest -ve no. Hope this works.

maxSoFar=currentSum=0;

for(i =0 to size){

currentSum+=a[i];

if(currentSum less than 0) //start a new window

currentSum=0;

if(currentSum greater then maxSoFar)

update maxSoFar to currentSum

}