An algorithm to find the length of the longest monotonically increasing…
2011
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?
- A.
The algorithm uses dynamic programming paradigm
- B.
The algorithm has a linear complexity and uses branch and bound paradigm
- C.
The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
- D.
The algorithm uses divide and conquer paradigm
Attempted by 63 students.
Show answer & explanation
Correct answer: A
Final answer: The algorithm uses the dynamic programming paradigm.
Algorithm (bottom-up DP):
Initialize L[n-1] = 1.
For i from n-2 down to 0 do:
If A[i] < A[i+1], set L[i] = 1 + L[i+1].
Otherwise set L[i] = 1.
Return max(L[0], L[1], ..., L[n-1]).
Why this is dynamic programming:
Each subproblem L_i is expressed in terms of a smaller subproblem L_{i+1}, showing optimal substructure.
Solutions to subproblems are reused (L_{i+1} is reused to compute L_i), which is the hallmark of dynamic programming. The implementation is a bottom-up (tabulation) DP.
Time and space complexity:
Time: O(n) because each element is processed once in a single pass.
Space: O(n) to store the L array. This can be reduced to O(1) extra space by tracking the current run length and the maximum length seen so far while scanning from right to left.
Why other paradigms are incorrect:
This is not divide and conquer because the algorithm does not split the array into independent subproblems that are solved separately and then combined.
This is not branch and bound because there is no search tree with pruning; the method deterministically computes values in one pass.