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.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

A. The longest subsequence where each number is larger than the previous one

B. The longest subsequence where each number is smaller than the previous one

C. The longest subsequence where numbers are equal

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the LIS definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   The longest subsequence where each number is larger than the previous one matches the definition exactly. Options B, C, and D do not describe LIS correctly.

3. Final Answer:

   The longest subsequence where each number is larger than the previous one -> Option A

4. Quick Check:

   LIS = longest increasing subsequence [OK]

Hint: LIS means strictly increasing sequence, not equal or decreasing [OK]

Common Mistakes:

• Confusing increasing with non-decreasing
• Thinking LIS means equal numbers
• Mixing up subsequence with substring

2. Which of the following C code snippets correctly initializes the array to store LIS lengths for each element in an array arr of size n?

easy

A. int lis[n] = {0};

B. int lis[n]; for(int i=0; i

C. int lis[n]; for(int i=0; i

D. int lis[n]; memset(lis, 1, n*sizeof(int));

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because each element alone is a subsequence.

2. Step 2: Check code correctness

   int lis[n]; for(int i=0; i

3. Final Answer:

   int lis[n]; for(int i=0; i -> Option B

4. Quick Check:

   Initialize LIS array with 1 [OK]

Hint: Initialize LIS array elements to 1, not 0 [OK]

Common Mistakes:

• Using memset to set integers to 1 (wrong)
• Initializing LIS array with zeros
• Not initializing LIS array at all

3. What is the output of the following C code snippet that calculates the length of LIS for array arr = {10, 22, 9, 33, 21, 50, 41, 60}?

int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = 8;
int lis[8];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Calculate LIS values step-by-step

   Start with lis = {1,1,1,1,1,1,1,1} - i=1: arr[1]=22 > arr[0]=10, lis[1]=max(1,1+1)=2 - i=2: arr[2]=9 no smaller than previous, lis[2]=1 - i=3: arr[3]=33 > 22 and 10, lis[3]=max(1,2+1)=3 - i=4: arr[4]=21 > 10 but <22, lis[4]=max(1,1+1)=2 - i=5: arr[5]=50 > 33, 22, 21, lis[5]=max(1,3+1)=4 - i=6: arr[6]=41 > 33, 22, 21, lis[6]=max(1,3+1)=4 - i=7: arr[7]=60 > 50, 41, lis[7]=max(1,4+1)=5

2. Step 2: Find maximum LIS length

   Maximum value in lis array is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   LIS length for given array = 5 [OK]

Hint: Trace LIS array updates carefully for each element [OK]

Common Mistakes:

• Counting non-increasing subsequences
• Forgetting to update lis[i] only if condition met
• Mixing up indices in nested loops

4. Identify the bug in the following C code snippet that attempts to compute the LIS length:

int arr[] = {3, 10, 2, 1, 20};
int n = 5;
int lis[5];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. LIS array should be initialized with 1, not 0

B. The nested loops should start from i=0

C. The condition arr[i] > arr[j] should be arr[i] >= arr[j]

D. The max variable should be initialized to 0

Solution

1. Step 1: Check LIS array initialization

   LIS array elements represent length of subsequence ending at each index. Each element alone forms subsequence of length 1, so initialize lis[i] = 1.

2. Step 2: Analyze effect of initialization

   Initializing lis[i] = 0 causes all comparisons lis[i] < lis[j] + 1 to fail or produce wrong results, leading to incorrect max LIS length.

3. Final Answer:

   LIS array should be initialized with 1, not 0 -> Option A

4. Quick Check:

   Initialize LIS array with 1 to avoid zero-length subsequences [OK]

Hint: Always start LIS lengths at 1, not 0 [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Changing comparison operators incorrectly
• Starting loops at wrong indices

5. Given an array arr = {5, 7, 4, 8, 6, 9}, write a C function to find the length of the Longest Increasing Subsequence using dynamic programming. What is the length of the LIS for this array?

hard

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Initialize LIS array with 1 for each element

   lis = {1,1,1,1,1,1}

2. Step 2: Update LIS values by comparing each element with previous ones

   - i=1 (7): 7 > 5, lis[1] = max(1, 1+1) = 2 - i=2 (4): 4 > 5? No, lis[2] = 1 - i=3 (8): 8 > 5, lis[3] = max(1,1+1)=2; 8 > 7, lis[3] = max(2,2+1)=3; 8 > 4, lis[3] = max(3,1+1)=3 - i=4 (6): 6 > 5, lis[4] = max(1,1+1)=2; 6 > 7? No; 6 > 4, lis[4] = max(2,1+1)=2; 6 > 8? No - i=5 (9): 9 > 5, lis[5] = max(1,1+1)=2; 9 > 7, lis[5] = max(2,2+1)=3; 9 > 4, lis[5] = max(3,1+1)=3; 9 > 8, lis[5] = max(3,3+1)=4; 9 > 6, lis[5] = max(4,2+1)=4

3. Step 3: Find maximum LIS length

   Maximum lis value is 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   LIS length for given array = 4 [OK]

Hint: Update LIS by checking all previous smaller elements [OK]

Common Mistakes:

• Not updating LIS correctly for all previous elements
• Confusing subsequence with substring
• Forgetting to initialize LIS array with 1