Longest Increasing Subsequence in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Increasing Subsequence (LIS) in an array?

The Longest Increasing Subsequence is the longest sequence of elements in the array such that each element is strictly greater than the previous one, and the elements are in the same order as in the original array but not necessarily contiguous.

intermediate

What is the time complexity of the classic dynamic programming approach to find LIS?

The classic dynamic programming approach to find LIS has a time complexity of O(n²), where n is the number of elements in the array.

advanced

What data structure helps optimize LIS calculation to O(n log n)?

A binary search technique on a temporary array (often called 'tails') helps optimize LIS calculation to O(n log n) by maintaining the smallest possible tail element for increasing subsequences of different lengths.

advanced

In LIS, why do we use binary search on the 'tails' array?

We use binary search on the 'tails' array to quickly find the position where the current element can replace an existing tail element or extend the sequence, ensuring the tails array remains sorted and minimal for subsequence lengths.

intermediate

What does the 'tails' array represent in the O(n log n) LIS algorithm?

The 'tails' array stores the smallest possible last element of an increasing subsequence of a given length. For example, tails[i] is the smallest tail of all increasing subsequences of length i+1 found so far.

What is the output length of LIS for the array [10, 9, 2, 5, 3, 7, 101, 18]?

A 6

B 4

C 5

D 3

The longest increasing subsequence is [2, 3, 7, 101], which has length 4.

Which approach has better time complexity for LIS: classic DP or binary search optimization?

A Classic DP with O(n²)

B Neither can solve LIS

C Both have same complexity

D Binary search optimization with O(n log n)

Binary search optimization reduces the time complexity to O(n log n), which is better than the classic DP approach of O(n²).

In the O(n log n) LIS algorithm, what does replacing an element in the 'tails' array signify?

A Improving the potential for longer subsequences

B Starting a new subsequence

C Extending the LIS length

D No effect on LIS

Replacing an element in 'tails' means we found a smaller tail for a subsequence of that length, improving chances to build longer subsequences later.

Which of these sequences is NOT strictly increasing?

A [10, 20, 30]

B [1, 3, 5, 7]

C [2, 2, 3, 4]

D [5, 6, 8, 9]

Sequence [2, 2, 3, 4] is not strictly increasing because 2 is repeated consecutively.

What is the minimum length of LIS in any non-empty array?

A 1

B 2

C 0

D Depends on array size

The minimum length of LIS is 1 because any single element is an increasing subsequence by itself.

Explain the difference between the classic dynamic programming approach and the binary search optimized approach for finding the Longest Increasing Subsequence.

Think about how the 'tails' array helps reduce comparisons.

Describe how the 'tails' array is updated during the O(n log n) LIS algorithm when processing each element.

Focus on how binary search helps maintain the tails array.

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