Longest Increasing Subsequence in DSA C++ - Deep Dive

Overview - Longest Increasing Subsequence

What is it?

The Longest Increasing Subsequence (LIS) is a sequence of numbers from a given list where each number is bigger than the one before it, and the sequence is as long as possible. It does not have to be made of consecutive numbers from the list, but the order must stay the same. For example, in the list [3, 10, 2, 1, 20], the LIS is [3, 10, 20]. This concept helps us find patterns and order in data.

Why it matters

Without the ability to find the longest increasing subsequence, many problems involving order and progression would be harder to solve efficiently. For example, in stock market analysis, finding the longest period of increasing prices helps investors. Without LIS, algorithms would be slower and less practical, making it difficult to analyze trends or optimize sequences in real life.

Where it fits

Before learning LIS, you should understand arrays, basic loops, and simple dynamic programming concepts. After mastering LIS, you can explore related topics like Longest Common Subsequence, patience sorting, and advanced dynamic programming optimizations.

Mental Model

Core Idea

The Longest Increasing Subsequence is the longest chain you can build by picking numbers in order, each bigger than the last.

Think of it like...

Imagine stacking books on a shelf where each book must be taller than the one below it. You want the tallest stack possible without changing the order of books on the shelf.

Input: [3, 10, 2, 1, 20]

Step-by-step:
3 -> start stack
3, 10 -> 10 is bigger, add on top
3, 10, 20 -> 20 is bigger, add on top

Resulting LIS: 3 -> 10 -> 20 -> null

Build-Up - 7 Steps

1

Foundation

Understanding Increasing Subsequences

Concept: Learn what an increasing subsequence is and how to identify one in a list.

An increasing subsequence is a set of numbers from the list where each number is bigger than the previous one. For example, in [1, 3, 2], subsequences like [1, 3] or [1, 2] are increasing. The subsequence does not need to be continuous but must keep the original order.

Result

You can spot increasing subsequences like [1, 3] or [1, 2] in a list.

Understanding what counts as an increasing subsequence is the first step to finding the longest one.

2

Foundation

Brute Force Approach to LIS

Concept: Try all possible subsequences to find the longest increasing one.

Check every subsequence of the list and see if it is increasing. Keep track of the longest one found. This method is simple but very slow because the number of subsequences grows exponentially.

Result

You can find the LIS but only for very small lists due to slow speed.

Brute force shows the problem clearly but is impractical for large data.

3

Intermediate

Dynamic Programming for LIS

🤔Before reading on: do you think storing the length of LIS ending at each element helps find the overall LIS? Commit to yes or no.

Concept: Use dynamic programming to store the length of the LIS ending at each position to avoid repeated work.

Create an array dp where dp[i] is the length of the LIS ending at index i. For each element, look back at previous elements smaller than it and update dp[i] = max(dp[i], dp[j] + 1). The answer is the max value in dp.

Result

For input [3, 10, 2, 1, 20], dp = [1, 2, 1, 1, 3], so LIS length is 3.

Storing intermediate results prevents repeated calculations and speeds up the solution from exponential to quadratic time.

4

Intermediate

Reconstructing the LIS Sequence

🤔Before reading on: do you think knowing only the length of LIS is enough to find the actual sequence? Commit to yes or no.

Concept: Track previous indices to rebuild the LIS after computing lengths.

Along with dp, keep an array prev to store the index of the previous element in the LIS. After filling dp, find the index with max dp value and follow prev links backward to reconstruct the LIS sequence.

Result

For [3, 10, 2, 1, 20], the LIS sequence reconstructed is [3, 10, 20].

Knowing how to reconstruct the sequence makes the solution practical, not just theoretical.

5

Intermediate

Optimized O(n log n) LIS Algorithm

🤔Before reading on: do you think binary search can help speed up LIS calculation? Commit to yes or no.

Concept: Use a clever method with binary search to build a list that helps find LIS length faster.

Maintain an array tails where tails[i] is the smallest possible tail of an increasing subsequence of length i+1. For each number, use binary search to find where it fits in tails and update tails accordingly. The length of tails is the LIS length.

Result

For [3, 10, 2, 1, 20], tails evolves as [3], [3,10], [2,10], [1,10], [1,10,20], so LIS length is 3.

Binary search reduces the time complexity from O(n^2) to O(n log n), making LIS efficient for large inputs.

6

Advanced

Recovering LIS in O(n log n) Time

🤔Before reading on: do you think the optimized method can also reconstruct the LIS sequence efficiently? Commit to yes or no.

Concept: Extend the optimized method to track predecessors and reconstruct the LIS sequence.

Along with tails, keep arrays to track indices and predecessors. After processing all elements, backtrack from the last index to build the LIS sequence in O(n) time.

Result

For [3, 10, 2, 1, 20], the reconstructed LIS is [3, 10, 20].

Combining speed and sequence reconstruction makes the optimized method fully practical.

7

Expert

LIS Variations and Applications

🤔Before reading on: do you think LIS can be adapted to solve problems beyond simple increasing sequences? Commit to yes or no.

Concept: LIS concepts extend to variations like Longest Non-Decreasing Subsequence, multidimensional LIS, and real-world problems like patience sorting and envelope nesting.

By adjusting comparison rules or dimensions, LIS algorithms solve complex problems such as finding the longest chain of envelopes or optimizing tasks. Understanding these variations helps apply LIS in diverse scenarios.

Result

LIS techniques solve many advanced problems efficiently.

Knowing LIS variations unlocks powerful tools for solving complex, real-world sequence problems.

Under the Hood

The LIS dynamic programming approach builds a table of solutions for smaller subproblems (LIS ending at each element). The optimized method uses a tails array to keep track of minimal possible ends of subsequences of different lengths, enabling binary search to quickly find where to place new elements. Internally, this reduces redundant comparisons and leverages sorted properties of tails.

Why designed this way?

The brute force method is too slow for large inputs. Dynamic programming was introduced to reuse results and avoid repeated work. The O(n log n) method was designed to optimize further by using binary search, a classic technique to speed up ordered data operations. This design balances simplicity and efficiency.

Input array: [3, 10, 2, 1, 20]

DP approach:
Index: 0  1   2  3  4
Value:3 10   2  1 20
DP:   1  2   1  1  3

Optimized tails:
Step 1: tails = [3]
Step 2: tails = [3, 10]
Step 3: tails = [2, 10]
Step 4: tails = [1, 10]
Step 5: tails = [1, 10, 20]

Length of tails = 3 (LIS length)

Myth Busters - 4 Common Misconceptions

Quick: Does the LIS have to be made of consecutive elements? Commit yes or no.

Common Belief: LIS must be made of consecutive elements in the list.

Reality: LIS can skip elements as long as the order is preserved; it does not require consecutive elements.

Why it matters: Believing LIS requires consecutive elements leads to wrong solutions and misses longer subsequences.

Quick: Is the LIS always unique? Commit yes or no.

Common Belief: There is only one unique longest increasing subsequence for any list.

Reality: Multiple different LIS sequences can exist with the same maximum length.

Why it matters: Assuming uniqueness can cause confusion when reconstructing sequences or comparing solutions.

Quick: Does the O(n log n) method find the actual LIS sequence by default? Commit yes or no.

Common Belief: The optimized O(n log n) method directly gives the LIS sequence.

Reality: It only gives the length by default; extra tracking is needed to reconstruct the sequence.

Why it matters: Without tracking, you only know the length, which limits practical use.

Quick: Can LIS be solved faster than O(n log n)? Commit yes or no.

Common Belief: There is a known algorithm faster than O(n log n) for LIS.

Reality: O(n log n) is the best known time complexity for LIS in the general case.

Why it matters: Expecting faster algorithms can waste time searching for non-existent solutions.

Expert Zone

1

The tails array in the O(n log n) method does not represent an actual subsequence but helps track potential ends, which is subtle but crucial.

2

Reconstructing the LIS from the optimized method requires careful bookkeeping of predecessors and indices, which is often overlooked.

3

LIS algorithms can be adapted to multidimensional data by defining custom comparison rules, expanding their applicability.

When NOT to use

LIS algorithms are not suitable when the problem requires strictly consecutive elements or when the sequence must satisfy additional constraints like sums or products. In such cases, sliding window or segment tree methods might be better.

Production Patterns

In real-world systems, LIS is used in version control to find longest chains of changes, in bioinformatics to analyze DNA sequences, and in finance to detect longest growth trends. Optimized LIS with sequence reconstruction is standard in competitive programming and interview problems.

Connections

Longest Common Subsequence

LIS is a special case of Longest Common Subsequence where one sequence is sorted.

Understanding LIS helps grasp LCS algorithms since both use dynamic programming and sequence comparison.

Patience Sorting

The O(n log n) LIS algorithm is inspired by the patience sorting card game technique.

Knowing patience sorting reveals the intuition behind the tails array and binary search in LIS.

Project Management Scheduling

LIS concepts relate to finding the longest chain of dependent tasks in scheduling.

Recognizing LIS patterns helps optimize task sequences and resource allocation in project planning.

Common Pitfalls

#1 Trying to find LIS by checking only consecutive elements.

Wrong approach:

for (int i = 0; i < n-1; i++) {
if (arr[i] < arr[i+1]) length++;
else length = 1;
}
// This only finds longest increasing contiguous subarray, not subsequence.

Correct approach:

Use dynamic programming to consider all previous elements for each position:
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
}
}

Root cause:

Confusing subsequence with subarray leads to incorrect solutions.

#2 Assuming the O(n log n) method's tails array is the LIS sequence.

Wrong approach:

Print tails array directly as the LIS sequence after binary search updates.

Correct approach:

Use additional arrays to track predecessors and reconstruct the LIS after processing all elements.

Root cause:

Misunderstanding the role of tails as helper structure, not the actual subsequence.

#3 Not initializing dp array properly in dynamic programming.

Wrong approach:

int dp[n]; // uninitialized
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
}
}

Correct approach:

int dp[n];
for (int i = 0; i < n; i++) dp[i] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
}
}

Root cause:

Forgetting to set base case dp[i] = 1 causes wrong results.

Key Takeaways

The Longest Increasing Subsequence finds the longest ordered chain of increasing numbers in a list, not necessarily consecutive.

Dynamic programming reduces the problem from exponential to quadratic time by storing intermediate results.

The O(n log n) method uses binary search on a helper array to speed up LIS length calculation significantly.

Reconstructing the actual LIS sequence requires extra tracking beyond just the length calculation.

LIS concepts extend to many real-world problems and variations, making it a powerful tool in algorithm design.

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