An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below.
Let $L_i$, denote the length of the longest monotonically increasing sequence starting at index $i$ in the array.
Initialize $L_{n-1} = 1$.
For all $i$ such that $0 \leq i \leq n-2$
$ L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases} $
Finally, the length of the longest monotonically increasing sequence is $\text{max} \:(L_0, L_1, \dots , L_{n-1}).$
Which of the following statements is TRUE?
- The algorithm uses dynamic programming paradigm
- The algorithm has a linear complexity and uses branch and bound paradigm
- The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
- The algorithm uses divide and conquer paradigm