Dynamic Programming and Sequence Processing Practice Questions for GATE DA

Solve 55+ Dynamic Programming and Sequence Processing practice questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Dynamic Programming and Sequence Processing

Chapter Roadmap

Your journey to mastering sequence-based dynamic programming.

1. Consecutive Sequence Lengths

Finding the longest contiguous subarray satisfying a condition.

2. Subsequence Lengths

Tackling non-contiguous sequences like LIS and LCS.

3. Advanced Variations

Matrix chain multiplication, edit distance, and complex states.

What you will master

Defining precise DP states for sequence problems.
Formulating correct recurrence relations.
Optimizing space complexity from $O (N)$ to $O (1)$ .
Avoiding common traps in boundary conditions.

Topic Hero: Dynamic Programming for Consecutive Sequence Lengths

Topic Hero: Consecutive Sequence Lengths

Focuses on finding the longest contiguous segment that satisfies a specific condition.

Extend

If condition met with previous element, add $1$ to previous segment.

Reset

If condition broken, start a new segment of length $1$ .

This local decision builds a global solution in $O (N)$ time.

Dynamic Programming and Sequence Processing: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Programming, Data Structures and Algorithms MCQ

In the recurrence relation for the longest non-decreasing contiguous subarray, when the condition $X [i - 1] \leq X [i]$ is satisfied, the update rule is $S [i] = 1 + S [i - 1]$ . What is the minimum possible value of $S [i]$ in this case?

A.
0
B.
S[i-1]
C.
2
D.
1

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the extend case of the recurrence relation.

Step 1: When the condition $X [i - 1] \leq X [i]$ is true, the recurrence gives $S [i] = 1 + S [i - 1]$ .

Step 2: The minimum possible value of any $S [j]$ is 1 (the base case). So the minimum value of $S [i - 1]$ is 1.

Step 3: Substituting: minimum $S [i] = 1 + 1 = 2$ .

Answer: C (2)

Question 2 · Programming, Data Structures and Algorithms MCQ

Consider the standard recurrence relation for finding the longest non-decreasing contiguous subarray, where $S [i]$ represents the length of the valid segment ending exactly at index $i$ . If the condition $X [i - 1] \leq X [i]$ is false (i.e., $X [i - 1] > X [i]$ ), what is the minimum possible value of $S [i]$ ?

A.
0
B.
1
C.
S[i-1]
D.
S[i-1] - 1

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the reset condition in the consecutive sequence DP recurrence.

Step 1: Recall the recurrence relation. For each index $i$ , we initialize $S [i] = 1$ . Then we check if $X [i - 1] \leq X [i]$ .

Step 2: If the condition is true, we extend: $S [i] = S [i] + S [i - 1]$ .

Step 3: If the condition is false ( $X [i - 1] > X [i]$ ), the segment breaks. We do not extend. The value $S [i]$ remains at its initialized value of 1.

Step 4: Therefore, when $X [i - 1] > X [i]$ , the minimum (and only) possible value of $S [i]$ is 1.

Answer: B (1)

Question 3 · Programming, Data Structures and Algorithms MCQ

For the array $X = [2, 4, 1, 3, 5]$ , the DP array $S$ for the longest non-decreasing contiguous subarray is computed. Which of the following statements about $S$ is true?

A.
S[3] = 2
B.
S[5] = S[4]
C.
S[4] \le S[3] + 1
D.
S[2] = 3

Correct Answer:

Step-by-Step Solution

Key idea: This is a tracing question that tests your understanding of the bounding property $S [i] \leq S [i - 1] + 1$ .

Step 1: Trace the DP array for $X = [2, 4, 1, 3, 5]$ .

$i = 1$ : $X [1] = 2$ . Base case. $S [1] = 1$ .
$i = 2$ : $X [2] = 4$ . Check: $2 \leq 4$ ? True. $S [2] = 1 + 1 = 2$ .
$i = 3$ : $X [3] = 1$ . Check: $4 \leq 1$ ? False. $S [3] = 1$ .
$i = 4$ : $X [4] = 3$ . Check: $1 \leq 3$ ? True. $S [4] = 1 + 1 = 2$ .
$i = 5$ : $X [5] = 5$ . Check: $3 \leq 5$ ? True. $S [5] = 2 + 1 = 3$ .

So $S = [1, 2, 1, 2, 3]$ .

Step 2: Check each option.

A: $S [3] = 2$ ? No, $S [3] = 1$ .
B: $S [5] = S [4]$ ? No, $3 \neq = 2$ .
C: $S [4] \leq S [3] + 1$ ? $2 \leq 1 + 1 = 2$ . Yes, this is true.
D: $S [2] = 3$ ? No, $S [2] = 2$ .

Answer: C

Question 4 · Programming, Data Structures and Algorithms MCQ

Given the DP array $S = [1, 1, 2, 1, 2]$ for a longest non-decreasing contiguous subarray problem, how many times does the segment reset (i.e., $S [i] = 1$ for $i > 1$ )?

A.
2
B.
1
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: This is a reverse-engineering question that tests your understanding of the DP array and the reset condition.

Step 1: Understand what a "reset" means.

A reset occurs when $S [i] = 1$ for $i > 1$ .
This happens when the condition $X [i - 1] \leq X [i]$ is false.
Note: $S [1] = 1$ is the base case, not a reset.

Step 2: Count the resets in $S = [1, 1, 2, 1, 2]$ .

$i = 1$ : $S [1] = 1$ . Base case, not a reset.
$i = 2$ : $S [2] = 1$ . This is a reset (since $i > 1$ ).
$i = 3$ : $S [3] = 2$ . Not a reset.
$i = 4$ : $S [4] = 1$ . This is a reset.
$i = 5$ : $S [5] = 2$ . Not a reset.

Step 3: Count the resets.

Resets occur at $i = 2$ and $i = 4$ .
Total resets = 2.

Answer: A (2)

Question 5 · Programming, Data Structures and Algorithms MCQ

For the array $X = [3, 1, 4, 1, 5]$ , the DP array $S$ for the longest non-decreasing contiguous subarray is computed. Which ONE of the following statements about $S$ is true?

A.
S[3] = 3
B.
S[4] = 2
C.
S[2] = 2
D.
S[5] = S[3]

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement evaluation question requiring you to trace the DP array and check each claim.

Step 1: Trace $S$ for $X = [3, 1, 4, 1, 5]$ using the non-decreasing condition $X [i - 1] \leq X [i]$ .

$i = 1$ : Base case. $S [1] = 1$ .
$i = 2$ : $3 \leq 1$ ? False. Reset. $S [2] = 1$ .
$i = 3$ : $1 \leq 4$ ? True. Extend. $S [3] = 1 + 1 = 2$ .
$i = 4$ : $4 \leq 1$ ? False. Reset. $S [4] = 1$ .
$i = 5$ : $1 \leq 5$ ? True. Extend. $S [5] = 1 + 1 = 2$ .
$S = [1, 1, 2, 1, 2]$ .

Step 2: Check each option.

A: $S [3] = 3$ ? No, $S [3] = 2$ .
B: $S [4] = 2$ ? No, $S [4] = 1$ .
C: $S [2] = 2$ ? No, $S [2] = 1$ .
D: $S [5] = S [3]$ ? Yes, both equal 2.

Answer: D

Question 6 · Programming, Data Structures and Algorithms MCQ

Given the DP array $S = [1, 2, 3, 1, 2]$ for a longest non-decreasing contiguous subarray problem, how many indices $i$ (where $1 \leq i \leq 5$ ) satisfy $S [i] > 1$ ?

A.
2
B.
4
C.
3
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct counting question on a given DP array. Check each position.

Step 1: List the values of $S$ :

$S [1] = 1$
$S [2] = 2$
$S [3] = 3$
$S [4] = 1$
$S [5] = 2$

Step 2: Check $S [i] > 1$ for each $i$ :

$i = 1$ : $1 > 1$ ? No.
$i = 2$ : $2 > 1$ ? Yes.
$i = 3$ : $3 > 1$ ? Yes.
$i = 4$ : $1 > 1$ ? No.
$i = 5$ : $2 > 1$ ? Yes.

Step 3: Count the indices where $S [i] > 1$ : indices 2, 3, and 5. That is 3 indices.

Answer: C (3)

Question 7 · Programming, Data Structures and Algorithms MCQ

For a longest non-decreasing contiguous subarray problem on an array of length 5, which ONE of the following DP arrays $S$ is impossible?

A.
S = [1, 1, 2, 3, 1]
B.
S = [1, 2, 1, 2, 1]
C.
S = [1, 2, 3, 1, 2]
D.
S = [1, 2, 3, 5, 1]

Correct Answer:

Step-by-Step Solution

Key idea: This is a feasibility check question. The recurrence relation imposes the constraint $S [i] \leq S [i - 1] + 1$ for all $i \geq 2$ .

Step 1: Recall why this constraint holds. At each step, $S [i]$ is either reset to 1 or extended to $1 + S [i - 1]$ . In both cases, $S [i] \leq S [i - 1] + 1$ .

Step 2: Check each option against this constraint.

A: $[1, 1, 2, 3, 1]$ . Check: $1 \leq 2$ ok, $2 \leq 2$ ok, $3 \leq 3$ ok, $1 \leq 4$ ok. Valid.
B: $[1, 2, 1, 2, 1]$ . Check: $2 \leq 2$ ok, $1 \leq 3$ ok, $2 \leq 2$ ok, $1 \leq 3$ ok. Valid.
C: $[1, 2, 3, 1, 2]$ . Check: $2 \leq 2$ ok, $3 \leq 3$ ok, $1 \leq 4$ ok, $2 \leq 2$ ok. Valid.
D: $[1, 2, 3, 5, 1]$ . Check: $2 \leq 2$ ok, $3 \leq 3$ ok, $5 \leq 4$ ? No! $5 > 3 + 1 = 4$ . Violation at $i = 4$ .

Step 3: Option D violates the constraint, so it is impossible.

Answer: D

Question 8 · Programming, Data Structures and Algorithms MCQ

Consider the standard DP recurrence for the longest non-decreasing contiguous subarray, where $S [i]$ denotes the length of the valid segment ending exactly at index $i$ . For an arbitrary array $X$ of length $N \geq 2$ , what is the minimum possible value of $S [N]$ ?

A.
0
B.
1
C.
2
D.
N

Correct Answer:

Step-by-Step Solution

Key idea: This is a boundary condition question testing the reset mechanism of the recurrence relation.

Step 1: Recall the recurrence. For each index $i$ , $S [i]$ is initialized to 1. If the condition $X [i - 1] \leq X [i]$ holds, $S [i]$ becomes $1 + S [i - 1]$ . Otherwise, it remains 1.

Step 2: The question asks for the minimum possible value of $S [N]$ for an array of length $N \geq 2$ .

Step 3: Can $S [N]$ be 0? No, because the recurrence explicitly initializes $S [i] = 1$ before checking the condition, and the value only increases.

Step 4: Can $S [N]$ be 1? Yes. If the last two elements are strictly decreasing (i.e., $X [N - 1] > X [N]$ ), the condition fails. The segment resets, and $S [N]$ remains at its initialized value of 1. For example, if $X = [2, 1]$ , then $S = [1, 1]$ , so $S [2] = 1$ .

Step 5: Therefore, the minimum possible value of $S [N]$ is 1.

Answer: B (1)

Question 9 · Programming, Data Structures and Algorithms MCQ

Consider the following two statements about the longest non-decreasing contiguous subarray problem: Assertion (A): For the array

X = [1, 2, 2, 3]

, the length of the longest non-decreasing contiguous subarray is 4. Reason (R): The condition for a non-decreasing sequence is

X [i - 1] < X [i]

(strictly less than). Which of the following is correct?

A.
Both A and R are true, and R is the correct explanation of A
B.
Both A and R are true, but R is NOT the correct explanation of A
C.
A is true, but R is false
D.
A is false, but R is true

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing your understanding of the non-decreasing condition.

Step 1: Evaluate Assertion (A).

For $X = [1, 2, 2, 3]$ , trace the DP array.
$S [1] = 1$ .
$i = 2$ : $1 \leq 2$ ? True. $S [2] = 2$ .
$i = 3$ : $2 \leq 2$ ? True. $S [3] = 3$ .
$i = 4$ : $2 \leq 3$ ? True. $S [4] = 4$ .
Maximum is 4. So A is true.

Step 2: Evaluate Reason (R).

R states the condition is $X [i - 1] < X [i]$ (strictly less than).
However, "non-decreasing" means $X [i - 1] \leq X [i]$ (less than or equal to).
The condition in R is for "strictly increasing", not "non-decreasing".
So R is false.

Step 3: Conclusion.

A is true, but R is false.

Answer: C

Question 10 · Programming, Data Structures and Algorithms MCQ

Match the arrays in List I with the length of their longest strictly increasing contiguous subarray in List II: List I: P.

[2, 2, 3]

[1, 2, 3]

[4, 3, 2]

[1, 1, 2]

List II: 1. 1 2. 2 3. 3

A.
P-2, Q-3, R-1, S-2
B.
P-1, Q-3, R-1, S-2
C.
P-2, Q-3, R-1, S-1
D.
P-2, Q-2, R-1, S-3

Correct Answer:

Step-by-Step Solution

Key idea: This is a match-the-following question testing the trap of confusing strictly increasing with non-decreasing.

Step 1: Trace each array for strictly increasing ( $X [i - 1] < X [i]$ ).

P: $[2, 2, 3]$
$S [1] = 1$ .
$i = 2$ : $2 < 2$ ? False. $S [2] = 1$ .
$i = 3$ : $2 < 3$ ? True. $S [3] = 2$ .
Max = 2. So P-2.

Q: $[1, 2, 3]$
$S = [1, 2, 3]$ . Max = 3. So Q-3.

R: $[4, 3, 2]$
$S = [1, 1, 1]$ . Max = 1. So R-1.

S: $[1, 1, 2]$
$S [1] = 1$ .
$i = 2$ : $1 < 1$ ? False. $S [2] = 1$ .
$i = 3$ : $1 < 2$ ? True. $S [3] = 2$ .
Max = 2. So S-2.

Step 2: Match: P-2, Q-3, R-1, S-2.

Answer: A

Try a question

Login to view the complete practice questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Dynamic Programming and Sequence Processing Practice Questions for GATE DA

Chapter Roadmap: Dynamic Programming and Sequence Processing

Chapter Roadmap

1. Consecutive Sequence Lengths

2. Subsequence Lengths

3. Advanced Variations

What you will master

Topic Hero: Dynamic Programming for Consecutive Sequence Lengths

Topic Hero: Consecutive Sequence Lengths

Extend

Reset

Dynamic Programming and Sequence Processing: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit