GateAI
Dynamic Programming

GATE CSE 2011 · Q25

MCQ1 markEasy

Time

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n−1]A[0:n-1] is given below. Let LiL_i denote the length of the longest monotonically increasing sequence starting at index ii in the array. Initialize Ln−1=1L_{n-1} = 1. For all ii such that 0≤i≤n−20 \le i \le n-2 Li={1+Li+1if A[i]<A[i+1]1OtherwiseL_i = \begin{cases} 1 + L_{i+1} & \text{if } A[i] < A[i+1] \\ 1 & \text{Otherwise} \end{cases} Finally the length of the longest monotonically increasing sequence is Max⁡(L0,L1,…,Ln−1)\operatorname{Max}(L_0, L_1, \dots, L_{n-1}). Which of the following statements is **TRUE**?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) The algorithm uses dynamic programming paradigm

Dynamic Programming

The algorithm computes LiL_i (the length of the longest contiguous monotonically increasing subarray starting at index ii) using the previously computed subproblem solution Li+1L_{i+1}:

Li={1+Li+1if A[i]<A[i+1]1otherwiseL_i = \begin{cases} 1 + L_{i+1} & \text{if } A[i] < A[i+1] \\ 1 & \text{otherwise} \end{cases}

Key observations:

  1. It solves smaller subproblems first (starting from i=n−1i = n-1 down to 00) and stores/reuses their optimal solutions to solve larger subproblems (optimal substructure and overlapping subproblems).

  2. This is the characteristic hallmark of the dynamic programming paradigm.

  3. The algorithm runs in linear time O(n)O(n) by doing a single pass from right to left.

Hence, the correct statement is (A).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Dynamic Programming previous year question is Q25 of the GATE CSE 2011 paper. Find more GATE CSE PYQs on Dynamic Programming in Algorithms, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Dynamic Programming PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Dynamic Programming in GATE CSE

Dynamic Programming has 7 GATE CSE PYQs across 6 papers from 2011 to 2026. 2 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2011.

How GATE tests Dynamic Programming

More from GATE CSE 2011

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2011 · Q25 · MCQ

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 Li denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize Ln-1 = 1. For all i such that 0 ≤ i ≤ n-2 Li = 1 + Li+1 & if A[i] < A[i+1] 1 & Otherwise Finally the length of the longest monotonically increasing sequence is Max(L0, L1, , Ln-1). Which of the following statements is TRUE?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.