91影视

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.

Consider $K\left(j\right)\frac{n!}{r!\left(n鈭�r\right)!}$denotes the maximum contiguous sequence鈥檚 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.

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{鈥�}\text{迟辞鈥�}n\right)\\ \text{鈥勨赌勨赌勨赌勨赌勨赌勨赌勨赌勨赌�}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{鈥�}\text{迟辞鈥�}n\right)\\ \text{鈥勨赌勨赌刬蹿鈥�}\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)$

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.