Question

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For example, if S is 5,15,-30,10,-5,40,10 then 5,15,-30 is a contiguous subsequence but 5,15,40 is not.
1. Give a linear-time 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.

Answer 1

Answer:

We made use of the dynamic programming method to solve a linear-time algorithm which is given below in the explanation section.

Explanation:

Solution

(1) By making use of the  dynamic programming, we can solve the problem in linear time.

Now,

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

Let G[t] represent the sum of a maximum sum contiguous sub-sequence ending exactly at index t

Thus, given that:

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

Then,

G[0] = A[0].

Using the above recurrence relation, we can compute the sum of the optimal sub sequence for array A, which would just be the maximum over G[i] for 0 <= i<= n-1.

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

Now the algorithm would be:

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 .