Longest Increasing Subsequence in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of the following C code that calculates the length of the Longest Increasing Subsequence (LIS) for the given array?

DSA C

#include <stdio.h>

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize];
    int max_len = 1;
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (max_len < dp[i]) {
            max_len = dp[i];
        }
    }
    return max_len;
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", lengthOfLIS(arr, size));
    return 0;
}

A 4

B 3

C 5

D 6

💡 Hint

Trace the dp array updates for each element to find the longest increasing subsequence length.

The longest increasing subsequence has length 4 (e.g., {2, 3, 7, 101} or {2, 5, 7, 18}). The code correctly computes and prints 4.

❓ Predict Output

intermediate

Output of LIS length with repeated elements

What is the output of the following C code that calculates the length of the Longest Increasing Subsequence (LIS) for the given array with repeated elements?

DSA C

#include <stdio.h>

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize];
    int max_len = 1;
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (max_len < dp[i]) {
            max_len = dp[i];
        }
    }
    return max_len;
}

int main() {
    int arr[] = {3, 4, 2, 8, 10, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", lengthOfLIS(arr, size));
    return 0;
}

A 4

B 5

C 3

D 6

💡 Hint

Check subsequences like {3,4,8,10} and {2,5} to find the longest increasing subsequence.

The longest increasing subsequence has length 4 (e.g., {3, 4, 8, 10}). The code correctly computes and prints 4.

❓ Predict Output

advanced

Output of LIS length using binary search optimization

What is the output of the following C code that calculates the length of the Longest Increasing Subsequence (LIS) using binary search optimization?

DSA C

#include <stdio.h>

int binarySearch(int* tail, int left, int right, int key) {
    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (tail[mid] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int tail[numsSize];
    int length = 1;
    tail[0] = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < tail[0])
            tail[0] = nums[i];
        else if (nums[i] > tail[length - 1])
            tail[length++] = nums[i];
        else {
            int pos = binarySearch(tail, -1, length - 1, nums[i]);
            tail[pos] = nums[i];
        }
    }
    return length;
}

int main() {
    int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", lengthOfLIS(arr, size));
    return 0;
}

A 5

B 4

C 6

D 7

💡 Hint

The binary search helps maintain the smallest possible tail values for subsequences of different lengths.

The longest increasing subsequence length for the array is 4, for example {0, 2, 10, 14}. The code returns 4.

🧠 Conceptual

advanced

Understanding LIS subsequence reconstruction

Which data structure is most suitable to reconstruct the actual Longest Increasing Subsequence after computing its length using dynamic programming?

A Priority queue to get maximum elements quickly

B Hash map to store element counts

C Stack to store indices of elements in reverse order

D Queue to store elements in order of appearance

💡 Hint

Think about how to retrieve the subsequence in correct order after tracing back from the end.

A stack is used to store indices while tracing back from the end of the LIS to the start, so popping from the stack gives the subsequence in correct order.

🔧 Debug

expert

Identify the bug in LIS length calculation code

What error does the following C code produce when run, and why?

DSA C

#include <stdio.h>

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize];
    int max_len = 1;
    for (int i = 0; i <= numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (max_len < dp[i]) {
            max_len = dp[i];
        }
    }
    return max_len;
}

int main() {
    int arr[] = {1, 3, 2, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", lengthOfLIS(arr, size));
    return 0;
}

A Runs correctly and returns 4

B Returns incorrect LIS length 3 instead of 4

C Compilation error due to missing return statement

D Segmentation fault due to out-of-bounds array access

💡 Hint

Check the loop boundary conditions carefully for array indexing.

The loop runs with i <= numsSize, which causes dp[i] and nums[i] to access out-of-bounds index numsSize, leading to segmentation fault.

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