Multiple choice

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 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?

  1. The algorithm uses dynamic programming paradigm.

  2. The algorithm has a linear complexity and uses branch and bound paradigm.

  3. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm.

  4. The algorithm uses divide and conquer paradigm.
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

This algorithm uses dynamic programming because it solves the problem by breaking it into smaller subproblems (L_i depends on L_{i+1]) and stores the results. It builds the solution bottom-up from the base case L[n-1] = 1. The complexity is O(n) linear time. It does not use branch and bound (which prunes search trees) or divide and conquer (which recursively splits problems).

Keep practicing — related questions