Longest Increasing Subsequence in DSA C++

Mental Model

Find the longest sequence of numbers that keep going up without rearranging the original order.

Analogy: Imagine climbing stairs where each step is higher than the last. You want to find the longest path going up without stepping down or skipping steps backwards.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
LIS length array: [1] -> [1] -> [1] -> [1] -> [1] -> [1] -> [1] -> [1]

Dry Run Walkthrough

Input: array: [10, 22, 9, 33, 21, 50, 41, 60]

Goal: Find the length of the longest increasing subsequence in the array

Step 1: Start with first element 10, LIS length is 1

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1

Why: Each element alone is a subsequence of length 1

Step 2: Check element 22: compare with 10, 22 > 10, update LIS length at 22 to 2

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1

Why: 22 can extend the subsequence ending at 10

Step 3: Check element 9: compare with 10 and 22, 9 is smaller, LIS length stays 1

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 1 -> 1 -> 1 -> 1 -> 1

Why: 9 cannot extend any previous increasing subsequence

Step 4: Check element 33: compare with 10,22,9; 33 > 22, update LIS length at 33 to 3

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 3 -> 1 -> 1 -> 1 -> 1

Why: 33 extends the subsequence ending at 22

Step 5: Check element 21: compare with 10,22,9,33; 21 > 10, update LIS length at 21 to 2

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 3 -> 2 -> 1 -> 1 -> 1

Why: 21 extends subsequence ending at 10 but not 22 or 33

Step 6: Check element 50: compare with all previous; 50 > 33, update LIS length at 50 to 4

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 1 -> 1

Why: 50 extends the longest subsequence ending at 33

Step 7: Check element 41: compare with all previous; 41 > 33, update LIS length at 41 to 4

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 4 -> 1

Why: 41 extends the subsequence ending at 33

Step 8: Check element 60: compare with all previous; 60 > 50 and 41, update LIS length at 60 to 5

Array: 10 -> 22 -> 9 -> 33 -> 21 -> 50 -> 41 -> 60
LIS lengths: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 4 -> 5

Why: 60 extends the longest subsequence ending at 50 or 41

Result:

Longest Increasing Subsequence length array: 1 -> 2 -> 1 -> 3 -> 2 -> 4 -> 4 -> 5
Answer: 5

Annotated Code

DSA C++

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

using namespace std;

int longestIncreasingSubsequence(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    vector<int> lis(n, 1); // Initialize LIS lengths to 1

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                lis[i] = max(lis[i], lis[j] + 1); // Update LIS length at i
            }
        }
    }

    return *max_element(lis.begin(), lis.end()); // Max LIS length
}

int main() {
    vector<int> nums = {10, 22, 9, 33, 21, 50, 41, 60};
    int result = longestIncreasingSubsequence(nums);
    cout << "Longest Increasing Subsequence length: " << result << endl;
    return 0;
}

vector<int> lis(n, 1); // Initialize LIS lengths to 1

Start with each element as subsequence length 1

for (int i = 1; i < n; ++i) {

Traverse array from second element to end

for (int j = 0; j < i; ++j) {

Check all previous elements before i

if (nums[i] > nums[j]) {

If current element can extend subsequence ending at j

lis[i] = max(lis[i], lis[j] + 1); // Update LIS length at i

Update LIS length at i if longer subsequence found

return *max_element(lis.begin(), lis.end()); // Max LIS length

Return the longest subsequence length found

Output

Longest Increasing Subsequence length: 5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements to update LIS length

Space: O(n) because we store LIS lengths for each element in an array

vs Alternative: This is better than checking all subsequences (which is exponential), but slower than advanced O(n log n) methods using binary search

Edge Cases

empty array

returns 0 because no subsequence exists

DSA C++

if (n == 0) return 0;

array with all equal elements

returns 1 because longest increasing subsequence is any single element

DSA C++

lis[i] = max(lis[i], lis[j] + 1); // Update LIS length at i

array with strictly decreasing elements

returns 1 because no element can extend previous ones

DSA C++

if (nums[i] > nums[j]) {

When to Use This Pattern

When you need to find the longest sequence of increasing numbers in order, think of the Longest Increasing Subsequence pattern because it helps track and build subsequences step by step.

Common Mistakes

Mistake: Updating LIS length without checking if current element is greater than previous elements
Fix: Add condition to update LIS only if nums[i] > nums[j]

Mistake: Not initializing LIS lengths to 1 for each element
Fix: Initialize LIS array with 1 because each element alone is a subsequence

Summary

Finds the length of the longest increasing subsequence in an array.

Use when you want to find the longest ordered sequence of increasing numbers without rearranging the array.

Remember to build LIS lengths by comparing each element with all previous smaller elements and updating lengths accordingly.

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