A contiguous subsequence of a list S is a subsequence made up of consecutive ele

Question

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5, 15, -30, 10, -5, 40, 10, then 15, -30, 10 is a contiguous subsequence but 5, 15, 40 is not. How many contiguous subsequences are there for a list of length n? Give a linear-time dynamic programming algorithm for the following task: Input: A list of numbers, a_1, ..., a_n Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero.) For the preceding example, the answer would be 10, -5, 40, 10, with a sum of 55.

Explanation / Answer

Answer -> 1

There are possible subsequences are :

= n + (n-1) + (n-2) + .......... + 1 = O(n*n)

Answer -> 2

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 G[t] denote the sum of a maximum sum contiguous subsequence ending exactly at index t

Thus, we have that:

G[t+1] = max{G[t] + A[t+1] ,A[t+1] } (for all   1<=t<= n-1)

Also,

G[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 G[i] for 0 <= i<= n-1.

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

Now the algorithm would look thus:

Create arrays G and V each of size n.

G[0] = A[0];

V[0] = 0;

max = G[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

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

If ( G[i-1] > 0)

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

V[i] = V[i-1];

Else

G[i] = A[i];

V[i] = i;

If ( G[i] > max)

max_start = V[i];

max_end = i;

max = G[i];

EndFor.

Output max_start and max_end.

The above algorithm takes O(n) time .

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.