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.