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 ≤ i ≤ n - 2

\(L_i=\left\{\begin{matrix}1+L_{i+1}&\rm if\ A[i]<A[i+1]\\\ 1&\rm otherwise\end{matrix}\right.\)

Finally the length of the longest monotonically increasing sequence is Max (L_{0}, L_{1}, ... L_{n-1}).

Which of the following statements is **TRUE**?

This question was previously asked in

GATE CS 2011 Official Paper

Option 1 : The algorithm uses dynamic programming paradigm

The correct answer is **Option 1.**

__Key Points__

- The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example ,a[] = {3, 10, 2, 1, 20} Output: Length of LIS = 3 The longest increasing subsequence is 3, 10, 20.
- We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and re-computation of same subproblems can be avoided by either using memorization or tabulation.
- If we closely observe the problem then we can convert this problem to longest Common Subsequence Problem. Firstly we will create another array of unique elements of original array and sort it. Now the longest increasing subsequence of our array must be present as a subsequence in our sorted array. That’s why our problem is now reduced to finding the common subsequence between the two arrays.

**Hence the correct answer is** *The algorithm uses dynamic programming paradigm.*