Longest Increasing Subsequence in DSA C++ - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with empty LIS array

↓

For each element in input array

↓

Find position in LIS to place element

↓

If element > all in LIS, append

↓

Else replace element at found position

↓

Repeat for all elements

↓

Length of LIS array = length of longest increasing subsequence

We build a list representing the smallest possible last elements of increasing subsequences of different lengths, updating it as we scan the input.

Execution Sample

DSA C++

int lengthOfLIS(vector<int>& nums) {
  vector<int> lis;
  for (int x : nums) {
    auto it = lower_bound(lis.begin(), lis.end(), x);
    if (it == lis.end()) lis.push_back(x);
    else *it = x;
  }
  return lis.size();
}

This code finds the length of the longest increasing subsequence by maintaining a list of smallest possible ends.

Execution Table

Step	Operation	Current Element	LIS Array Before	Position Found	LIS Array After	Visual State
1	Process element	10	[]	0 (empty)	[10]	[10]
2	Process element	9	[10]	0 (replace 10)	[9]	[9]
3	Process element	2	[9]	0 (replace 9)	[2]	[2]
4	Process element	5	[2]	1 (append)	[2,5]	[2] -> [5]
5	Process element	3	[2,5]	1 (replace 5)	[2,3]	[2] -> [3]
6	Process element	7	[2,3]	2 (append)	[2,3,7]	[2] -> [3] -> [7]
7	Process element	101	[2,3,7]	3 (append)	[2,3,7,101]	[2] -> [3] -> [7] -> [101]
8	Process element	18	[2,3,7,101]	3 (replace 101)	[2,3,7,18]	[2] -> [3] -> [7] -> [18]
9	End	N/A	[2,3,7,18]	N/A	[2,3,7,18]	Length = 4

💡 All elements processed; LIS array length is 4, which is the length of the longest increasing subsequence.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
nums	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]	[10,9,2,5,3,7,101,18]
lis	[]	[10]	[9]	[2]	[2,5]	[2,3]	[2,3,7]	[2,3,7,101]	[2,3,7,18]	[2,3,7,18]
position	N/A	0	0	0	1	1	2	3	3	N/A

Key Moments - 3 Insights

Why do we replace elements in the LIS array instead of always appending?

Replacing elements keeps the LIS array representing the smallest possible last elements for subsequences of each length, allowing longer subsequences later. See steps 2 and 3 in execution_table where 10 and 9 are replaced by smaller numbers.

Why do we use lower_bound to find the position in the LIS array?

lower_bound finds the first element not less than the current element, which is the correct position to replace or append to maintain sorted order. This is shown in the 'Position Found' column in execution_table.

Does the LIS array represent the actual subsequence?

No, the LIS array length is correct, but the elements may not form a valid subsequence from the original array. It only helps find the length efficiently, as seen in the final LIS array [2,3,7,18].

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the LIS array after processing element 3?

A [2,5]

B [3,5]

C [2,3]

D [2,3,5]

💡 Hint

Check the 'LIS Array After' column at step 5 in execution_table.

At which step does the LIS array length first become 3?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'LIS Array After' column and count elements at each step.

If the input array started with [1, 2, 3] instead of [10, 9, 2], how would the LIS array after step 3 change?

A [1, 2, 3]

B [3]

C [2, 3]

D [1]

💡 Hint

Consider how elements are appended when each new element is greater than all in LIS array.

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Maintain a list 'lis' for smallest possible ends of increasing subsequences.
- For each element, find position with lower_bound in 'lis'.
- Replace element at position or append if larger than all.
- Length of 'lis' is length of LIS.
- Efficient O(n log n) approach using binary search.

Full Transcript

The Longest Increasing Subsequence problem finds the length of the longest sequence of increasing numbers in an array. We keep a list called 'lis' that stores the smallest possible last elements of increasing subsequences of different lengths. For each number, we find where it fits in 'lis' using binary search (lower_bound). If it is larger than all elements, we append it. Otherwise, we replace the first element in 'lis' that is not less than the current number. This way, 'lis' always represents the smallest ends, allowing longer subsequences later. The length of 'lis' at the end is the length of the longest increasing subsequence. The code runs efficiently in O(n log n) time. The execution table shows each step with the current element, position found, and how 'lis' changes. Key moments clarify why we replace elements and how 'lis' does not represent the actual subsequence but helps find its length.

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