Longest Increasing Subsequence in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the length of LIS ending at each element to 1.

DSA C

for (int i = 0; i < n; i++) {
    lis[i] = [1];
}

Drag options to blanks, or click blank then click option'

A1

Bi

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing lis[i] to 0 will cause incorrect LIS length calculation.

Using i or n as initial values is incorrect because lis[i] stores lengths, not indices.

Each element alone is a subsequence of length 1, so we initialize lis[i] to 1.

2fill in blank

medium

Complete the code to check if the current element can extend the LIS ending at a previous element.

DSA C

if (arr[j] [1] arr[i] && lis[j] + 1 > lis[i]) {
    lis[i] = lis[j] + 1;
}

Drag options to blanks, or click blank then click option'

A<

B==

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' will check for decreasing subsequence, which is incorrect here.

Using '==' or '!=' does not ensure increasing order.

We check if arr[j] is less than arr[i] to ensure the subsequence is increasing.

3fill in blank

hard

Fix the error in the code to update the maximum LIS length found so far.

DSA C

if (lis[i] [1] max_lis) {
    max_lis = lis[i];
}

Drag options to blanks, or click blank then click option'

A==

B<

C<=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' will update max_lis incorrectly to smaller values.

Using '==' or '<=' will not update max_lis properly.

We update max_lis only if lis[i] is greater than the current max_lis.

4fill in blank

hard

Fill both blanks to complete the nested loops for LIS calculation.

DSA C

for (int i = 1; i [1] n; i++) {
    for (int j = 0; j [2] i; j++) {
        // update lis[i]
    }
}

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes out-of-bound errors.

Using '>' or '>=' reverses loop direction incorrectly.

The outer loop runs from 1 to n-1 (i < n), and inner loop runs from 0 to i-1 (j < i).

5fill in blank

hard

Fill all three blanks to complete the LIS function return statement and variable declaration.

DSA C

int longest_increasing_subsequence(int arr[], int n) {
    int lis[n];
    int max_lis = [1];

    for (int i = 0; i < n; i++) {
        lis[i] = [2];
    }

    for (int i = 1; i [3] n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && lis[j] + 1 > lis[i]) {
                lis[i] = lis[j] + 1;
            }
        }
        if (lis[i] > max_lis) {
            max_lis = lis[i];
        }
    }
    return max_lis;
}

Drag options to blanks, or click blank then click option'

A0

B1

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing max_lis to 1 causes incorrect max calculation.

Initializing lis[i] to 0 causes wrong LIS lengths.

Using '<=' in loop causes out-of-bound errors.

max_lis starts at 0, lis[i] initialized to 1, and loop runs while i < n.