Question

A contiguous subsequence of a list $\mathbf{S}$is a subsequence made up of consecutive elements of $\mathbf{S}$. For instance, if $\mathbf{S}$is $\mathbf{5}\mathbf{,}\mathbf{}\mathbf{15}\mathbf{,}\mathbf{}\mathbf{-}\mathbf{30}\mathbf{,}\mathbf{}\mathbf{10}\mathbf{,}\mathbf{}\mathbf{-}\mathbf{5}\mathbf{,}\mathbf{}\mathbf{40}\mathbf{,}\mathbf{}\mathbf{10}$

then$\mathbf{15}\mathbf{,}\mathbf{}\mathbf{-}\mathbf{30}\mathbf{,}\mathbf{}\mathbf{10}$ is a contiguous subsequence but$\mathbf{5}\mathbf{,}\mathbf{15}\mathbf{,}\mathbf{}\mathbf{40}$ is not. Give a linear-time algorithm for the following task:Input: A list of numbers ${\mathbf{a}}_{\mathbf{1}}\mathbf{,}{\mathbf{a}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}\mathbf{,}{\mathbf{a}}_{\mathbf{n}}$.

Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).For the preceding example, the answer would be $\mathbf{10}\mathbf{,}\mathbf{}\mathbf{-}\mathbf{5}\mathbf{,}\mathbf{}\mathbf{40}\mathbf{,}\mathbf{}\mathbf{10}$, with a sum of 55. (Hint: For each $\mathit{j}\mathbf{\in }\left\{1,2,...,n\right\}$, consider contiguous subsequences ending exactly at position j.)

Short answer

The algorithm to find contiguous subsequence of maximum sum is implemented using dynamic programming in linear time.

Step-by-step solution

Define Dynamic Programming

Dynamic programming is used to solve the problem efficiently having the following two properties:

1. Overlapping Subproblems
2. Optimal Substructure

Dynamic programming is used for the problem that can be divided into subproblems and the solution of subproblems can be reused to solve the problem. So, optimal solution of the problem is constructed using the optimal solution of subproblems.

Determine the recurrence relation to find continuous subsequence with maximum sum

Consider $K\left(j\right)\frac{n!}{r!\left(n-r\right)!}$denotes the maximum contiguous sequence’s sum.

Here, represent the index at which the sequence ends.

For $K\left(j+1\right)$, there are two possible options:

1. Start new contiguous sequence with sum $a_{j+1}$.
2. Add the next value in the previous calculated sum$K\left(j\right)$.

Thus, the recurrence is written as:

$K\left(j\right)=\text{MAX}\left(K\left(j-1\right)+a_j,a_j\right)$

This is recursive call on$K\left(j\right)$ which will add contiguous subsequence if it is encapsulate in a loop.

Determine the algorithm to find continuous subsequence with maximum sum

Consider a variable w to hold the maximum sum. The algorithm to find contiguous subsequence of maximum sum is as follows:

$\begin{array}{l}K\left(0\right)=0\\ \text{for}\left(j=1\text{to\hspace{0.33em}}n\right)\\ K\left(j\right)=\text{MAX}\left(0,K\left(j-1\right)+x_j\right)\\ s=k\left[j\right]\\ i=0\\ j=0\\ k=0\end{array}$

$\begin{array}{l}\text{for}\left(i=0\text{to\hspace{0.33em}}n\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}if\hspace{0.33em}}\left(K\left(i\right)>s\right)\end{array}$

Then update new value of$s$ as maximum value of contiguous subsequence

if$\left(K\left(i\right)=0\right)$ and$i<k$

Then set$j=j+1$

return$\left(j,\mathrm{...},k\right)$

Determine the time complexity of algorithm

The first loop will take$O\left(n\right)$ time to execute as it executes for n times. The second loop will take$O\left(n+1\right)$ time to execute as it is executed$n+1$ times. The time complexity of entire program is$O\left(2n+1\right)$ which is asymptotically equal to $O\left(n\right)$.

Thus, the algorithm takes linear time.