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.

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 .

you can not change you age soon as you signed up. the only way is too delete your account and use another account to sign up and put your correct age.

c a goverment agency or homeowner