GATE CS 2024 Set 2 — Question 35

NAT+1 / -0MediumLongest Increasing SubsequenceDynamic ProgrammingAlgorithms

Algorithms → Dynamic Programming → Longest Increasing Subsequence

Last updated 20 August 2026

Question

Let

A

be an array containing integer values. The distance of

A

is defined as the minimum number of elements in

A

that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array

[2, 5, 3, 1, 4, 2, 6]

is ___________

Correct answer

3 to 3

Solution

To minimize the number of replacements required to make the array sorted in non-decreasing order, we should keep the maximum number of elements from the original array that already form a non-decreasing subsequence. The remaining elements will be replaced.

Let

n

be the length of the array. The minimum number of replacements is given by:

\text{Distance} = n - \text{Length of Longest Non-Decreasing Subsequence (LNDS)}

The given array is

A = [2, 5, 3, 1, 4, 2, 6]

. The length

n = 7

Let's find the Longest Non-Decreasing Subsequence:

1.Start with the first element:

[2]

2.Next is 5 (

5 \ge 2

[2, 5]

3.Next is 3. It breaks the order with 5. We can form

[2, 3]

(replacing 5 in the active list of potential end values).

4.Next is 1. It breaks the order with 2. We can form

[1, 3]

5.Next is 4 (

4 \ge 3

[1, 3, 4]

6.Next is 2. It breaks the order with 3. We can form

[1, 2, 4]

7.Next is 6 (

6 \ge 4

[1, 2, 4, 6]

The length of the LNDS is 4. One such subsequence is

[2, 3, 4, 6]

(indices 0, 2, 4, 6).

Therefore, the minimum number of replacements is:

7 - 4 = 3

GATE CS 2024 Set 2 — Question 35

Question

Correct answer

Solution

More questions on Dynamic Programming