Dynamic Programming – Maximum sum contiguous subsequence

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are n+ (n-1) + (n-2) + ... + 1 = O(n^2) possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be O(n^3).

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

for (int i = 0; i < n ; i++)

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

————

APPROACH 2:

We can improve the running time to O(n^2) by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i … j+1] = A[j+1] + sum of the subsequence A[i … j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

for (int i = 0; i < n; i++)

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of O(n).

Let S[k] denote the sum of a maximum sum contiguous subsequence ending exactly at index k.

Thus, we have that:

S[k+1] = max \{S[k] + A[k+1], A[k+1] \} (for all 1 \leq k \leq n-1)

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over S[i] for 0 \leq i \leq n-1.

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array T where T[i] would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

max = S[i];

EndFor.

Output max_start and max_end.

———–

The above algorithm takes O(n) time and O(n) space.

——–

We can however improve upon the space requirements, reducing it to O(1). The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all n values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

max = S;

End For.

Output max_end and max_start.

———–

The above algorithm takes O(n) time and O(1) space.

———-

11 Responses to Dynamic Programming – Maximum sum contiguous subsequence

  1. progcoders says:

    IN the above of dynamic program… where is the max variable used ??

    • tkramesh says:

      Sorry, the max variable wasn’t being tracked earlier. The post has been updated now to track the max variable. Whenever the sum is greater than max, max is set to be equal to the sum. Thanks.

  2. Arael says:

    excuse me
    has anyone implemented the code ?
    i did and it shows a wrong answer

    • tkramesh says:

      Thanks for pointing it out.

      The max variables used in the code were not being updated earlier. That has now been changed. So it might work fine now. However, I must add a disclaimer that I have not tested this code, so it’s possible it might not still work.

  3. Still Water says:

    you did not track your max variable, you need to update max

  4. Clark says:

    Thanks for posting the nice algorithm. I will probably code it up. I will send you the link if I do.

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: