GATE Computer Science (CS) 2011 Solved Paper

Question : 35 of 65

Marks: +1, -0

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} = {\{\table 1 + L_{i + 1} , \text"if A[i]" < A[i + 1] ; \text" 1" , otherwise ; }.

Finally the length of the longest monotonically increasing sequence is Max (L₀, L₁, ... 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.

Validate

Go to Question:

Prev Question

Next Question