Home > Applied Algorithms, Arrays, Dynamic Programming > Maximum Value Contiguous Subsequence (Maximum Contiguous Sum)

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

Advertisements
  1. June 14, 2012 at 9:53 am

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

  2. Argus
    October 21, 2012 at 10:09 pm

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

    • June 24, 2013 at 12:32 pm

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

  3. Victor
    December 27, 2012 at 5:37 pm

    ” 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…

  4. Rahul
    January 30, 2013 at 10:06 am

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

    answer is 11 {2,-1,10}

  5. November 27, 2013 at 8:57 pm

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

  6. madhura
    September 29, 2014 at 3:41 pm

    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.

    • madhura
      September 29, 2014 at 3:50 pm

      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
      }

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: