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)?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int lengthOfLIS(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    std::vector<int> dp(nums.size(), 1);
    for (size_t i = 1; i < nums.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << lengthOfLIS(nums) << std::endl;
    return 0;
}

A 4

B 6

C 5

D 3

💡 Hint

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

The longest increasing subsequence is {2, 3, 7, 101}, which has length 4.

🧠 Conceptual

intermediate

Understanding LIS with binary search optimization

Which statement correctly describes the role of the 'tails' array in the binary search approach to find the length of the Longest Increasing Subsequence?

A 'tails' contains all elements of the input sorted in ascending order.

B 'tails' is used to store the indices of the longest decreasing subsequence.

C 'tails[i]' holds the smallest possible tail value of an increasing subsequence of length i+1.

D 'tails' stores the actual longest increasing subsequence found so far.

💡 Hint

Think about how 'tails' helps to maintain potential ends of subsequences.

'tails[i]' is the smallest tail of all increasing subsequences with length i+1, allowing efficient updates and binary search.

🔧 Debug

advanced

Identify the runtime error in LIS code

What runtime error will the following code produce when executed?

DSA C++

#include <iostream>
#include <vector>

int lengthOfLIS(std::vector<int>& nums) {
    std::vector<int> dp(nums.size(), 1);
    for (int i = 1; i <= nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    int max_len = 0;
    for (int val : dp) {
        if (val > max_len) max_len = val;
    }
    return max_len;
}

int main() {
    std::vector<int> nums = {3, 10, 2, 1, 20};
    std::cout << lengthOfLIS(nums) << std::endl;
    return 0;
}

A No error, outputs 3

B Segmentation fault due to out-of-bounds access

C Compilation error due to type mismatch

D Logic error, outputs 0

💡 Hint

Check the loop conditions and array indexing carefully.

The loop uses i <= nums.size(), which causes i to go out of bounds when accessing nums[i] and dp[i].

📝 Syntax

advanced

Syntax error in LIS code snippet

Which option correctly fixes the syntax error in this LIS code snippet?

DSA C++

std::vector<int> dp(nums.size(), 1)
for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            dp[i] = std::max(dp[i], dp[j] + 1);
        }
    }
}

A Change 'for' to 'foreach' in the loops

B Remove the braces around the inner if statement

C Replace 'std::max' with 'max' without including <algorithm>

D Add a semicolon after the first line: std::vector<int> dp(nums.size(), 1);

💡 Hint

Check the end of each statement for missing punctuation.

The vector initialization line is missing a semicolon, causing a syntax error.

🚀 Application

expert

Longest Increasing Subsequence reconstruction

Given the following code that computes the length of LIS, what is the printed output representing the actual LIS sequence?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> nums = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9};
    std::vector<int> dp(nums.size(), 1);
    std::vector<int> prev(nums.size(), -1);

    int max_len = 1, max_index = 0;
    for (size_t i = 1; i < nums.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            max_index = i;
        }
    }

    std::vector<int> lis_sequence;
    for (int i = max_index; i >= 0; i = prev[i]) {
        lis_sequence.push_back(nums[i]);
        if (prev[i] == -1) break;
    }
    std::reverse(lis_sequence.begin(), lis_sequence.end());

    for (int num : lis_sequence) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

A 0 4 6 9

B 0 4 6 14

C 0 2 6 9

D 0 4 10 14

💡 Hint

Trace the prev array to reconstruct the LIS from the maximum dp index.

The LIS is {0, 4, 6, 9} with length 4, reconstructed by following prev indices from max_index.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask for in a given sequence of numbers?

easy

A. The longest subsequence where numbers are equal

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

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

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the problem definition

   The LIS problem looks for a subsequence where every next number is bigger than the one before it.

2. Step 2: Compare options with the definition

   The longest subsequence where each number is larger than the previous one matches the definition exactly, others describe different or incorrect sequences.

3. Final Answer:

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

4. Quick Check:

   LIS means increasing subsequence = The longest subsequence where each number is larger than the previous one [OK]

Hint: LIS means strictly increasing numbers in order [OK]

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous subarray
• Assuming equal numbers count as increasing

2. Which of the following is the correct way to declare a vector for storing LIS lengths in C++?

easy

A. std::vector<int> lis(n, 1);

B. vector<int> lis(n);

C. std::vector lis(n, 0);

D. vector lis<int>(n, 1);

Solution

1. Step 1: Check correct vector declaration syntax

   In C++, std::vector<int> lis(n, 1); creates a vector of size n with all values initialized to 1.

2. Step 2: Validate each option

   std::vector<int> lis(n, 1); uses correct syntax and initialization. vector<int> lis(n); misses initialization, C misses template argument, D has wrong template syntax.

3. Final Answer:

   std::vector<int> lis(n, 1); -> Option A

4. Quick Check:

   Correct vector syntax with initialization = std::vector<int> lis(n, 1); [OK]

Hint: Use std::vector<int> name(size, initial_value) [OK]

Common Mistakes:

• Omitting std:: or using wrong template syntax
• Not initializing vector values
• Using wrong brackets or missing template argument

3. What is the output of the following C++ code snippet?

std::vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.size();
std::vector<int> lis(n, 1);
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max_lis = 0;
for (int i = 0; i < n; i++) {
  if (lis[i] > max_lis) max_lis = lis[i];
}
std::cout << max_lis << std::endl;

medium

A. 3

B. 4

C. 6

D. 5

Solution

1. Step 1: Trace LIS calculation for each element

   Calculate lis array step-by-step: lis = [1,2,1,3,2,4,4,5]

2. Step 2: Find maximum value in lis array

   Maximum lis value is 5, which is printed as output.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Max LIS length = 5 [OK]

Hint: Track lis array updates to find max length [OK]

Common Mistakes:

• Confusing subsequence with subarray
• Not updating lis[i] correctly
• Forgetting to find max after loops

4. Identify the bug in this LIS code snippet:

std::vector<int> arr = {3, 10, 2, 1, 20};
int n = arr.size();
std::vector<int> lis(n, 1);
for (int i = 0; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max_lis = *max_element(lis.begin(), lis.end());
std::cout << max_lis << std::endl;

medium

A. Missing check if lis[i] < lis[j] + 1 before updating

B. Wrong initialization of lis vector

C. Incorrect loop ranges for i and j

D. Using max_element incorrectly

Solution

1. Step 1: Analyze update condition inside nested loops

   The code updates lis[i] without checking if lis[j] + 1 is greater, causing wrong LIS values.

2. Step 2: Identify missing condition

   Adding 'if (lis[i] < lis[j] + 1)' before update fixes the bug.

3. Final Answer:

   Missing check if lis[i] < lis[j] + 1 before updating -> Option A

4. Quick Check:

   Update only if new LIS is longer [OK]

Hint: Always check if new LIS length is greater before update [OK]

Common Mistakes:

• Updating lis[i] blindly overwrites correct values
• Confusing loop indices
• Incorrect use of max_element function

5. Given the sequence {5, 7, 4, 8, 6, 9}, what is the length of the Longest Increasing Subsequence if you must also ensure the subsequence elements are at even indices only (0-based)?

medium

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Identify even indices (0-based)

   Positions 0, 2, 4 have values 5, 4, 6.

2. Step 2: Compute LIS on {5, 4, 6}

   Possible increasing subsequences: {5, 6} or {4, 6}, both length 2. No length 3 possible (5 > 4).

3. Final Answer:

   2 -> Option C

4. Quick Check:

   LIS length on even indices only = 2 [OK]

Hint: Filter even indices first, then find LIS [OK]

Common Mistakes:

• Ignoring index restriction
• Using full sequence instead of filtered
• Assuming contiguous subsequence