Dynamic Programming – 1 : Maximum value contiguous subsequence

In the following sequence of posts, we shall look at a few dynamic programming problems, and their solutions. Please take a look at http://people.csail.mit.edu/bdean/6.046/dp/ for nice animations on solving dynamic programming problems.

In this post, we shall look at the maximum value contiguous subsequence problem.

The problem can be stated as follows: We have a sequence A(1), A(2), …, A(n). We need to find a contiguous subsequence A(i … j) such that the sum of elements in that subsequence is maximum over all subsequences.

Note that there could be more than one subsequence having the maximum sum.

Note also that if all the elements in A are non-negative, the entire subsequence is a solution.

Let us consider a sequence having both positive and negative values.

Let us denote by S(i, j) the sum of elements in the subsequence A(i…j), i.e. $S(i,j) = \sum_{k} A(k)$, where k goes from i to j.

Now, we want a subsequence whose sum is maximum. The maximum sum is $\sum_{j} \sum_{i} S(i,j)$.

Now, this is essentially, $\sum_j M(j)$, where $M(j) = \sum_i S(i,j)$.

In plain English, $M(j)$ is the maximum sum of a contiguous subsequence ending at element A(j).

Now, let us try to find a recursive formula for computing M(j). What we basically want is to express M(j) in terms of M(p) values where $p < j$.

Now, a contiguous subsequence ending at A(j) must necessarily contain A(j). It may or may not contain elements before A(j). If we are going to consider A(j-1) and the previous elements, we might as well consider the maximum contiguous subsequence ending at A(j-1).

Hence, we have the following:

$M(j) = max \{ M(j-1) + A(j), A(j) \}$

—-

Note that it takes O(1) to compute any given $M(j)$ value given the $M(j-1)$ value. We can compute all M(j) values in a bottom up fashion in $O(n)$ time.

Finding the maximum among them can again be done in $O(n)$ time.

If we keep track of the $i$ values of the subsequences while computing the $M(j)$ values, we would also have the starting and ending indexes of a maximum value subsequence.

—-

Hence, the running time is $O(n)$.

The additional space requirement (that is, the space required in addition to $O(n)$ to store the sequence) is O(1) since we are only interested in $M(j-1)$ for computing $M(j)$.

—-