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 .
