Longest Increasing Subsequence: DP and Optimized Solutions

1. The Longest Increasing Subsequence Problem

A subsequence, as we recall, is formed by deleting zero or more elements from a sequence without changing the order of the remaining elements. An increasing subsequence is a subsequence where the elements are in strictly increasing order. The goal of the LIS problem is to find the length of the longest such subsequence in a given array.

For example, in the array [10, 9, 2, 5, 3, 7, 101, 18]:

• [2, 3, 7, 18] is an increasing subsequence.
• [2, 3, 7, 101] is another, longer, increasing subsequence.
• The LIS is [2, 3, 7, 101] (or [2, 5, 7, 101], etc.), and its length is 4.

2. The Standard DP Approach: O(n²)

Just like with other DP problems, the key is to define a subproblem. For LIS, a very effective way to define the state is:

Let dp[i] be the length of the Longest Increasing Subsequence that ends at index i.

With this definition, how can we compute dp[i]? The LIS ending at index i will be formed by taking the element nums[i] and appending it to some LIS that ends at a previous index j (where j < i), provided that nums[j] < nums[i]. To get the longest possible sequence ending at i, we should look for the maximum length among all valid previous subsequences.

This leads to the recurrence relation:
dp[i] = 1 + max(dp[j]) for all 0 <= j < i where nums[j] < nums[i].

The + 1 accounts for the element nums[i] itself. If no such j exists (i.e., nums[i] is smaller than all preceding elements), then the LIS ending at i is just the element itself, so dp[i] = 1. This serves as our base case.

The following video provides an excellent visualization of this process. It frames the problem as finding the longest path in a Directed Acyclic Graph (DAG), which is a powerful way to think about many DP problems.

Implementation and Final Answer

After computing the dp array for all indices, the job is not quite done. Remember that dp[i] is the length of the LIS ending at i. The overall LIS of the entire array could end at any index. Therefore, the final answer is the maximum value in the dp array.

Let's look at a concise Java implementation of this logic.

The time complexity is O(n²) due to the nested loops, and the space complexity is O(n) for the dp array. This is a solid solution and a great starting point.

3. The Optimized Approach: O(n log n)

An O(n²) solution is often too slow for competitive programming or interviews involving large datasets (e.g., n = 10⁵). We can do better. The bottleneck in our previous approach was the inner loop: for each element, we linearly scanned all previous elements. We can optimize this search.

The core idea is to maintain an auxiliary array (let's call it tails) that stores the smallest possible tail element for an increasing subsequence of a given length.
Specifically, tails[i] will hold the smallest tail element of all increasing subsequences that have a length of i+1.

By its definition, this tails array will always be sorted. This is the key property that allows for optimization.

Here’s the algorithm:

1. Initialize an empty list tails.
2. Iterate through each number num in the input array nums.
3. For each num, use binary search on tails to find the first element that is greater than or equal to num.
   • Case 1: num is greater than all elements in tails. This means num can extend the longest subsequence found so far. We append num to tails. The length of the LIS increases by 1.
   • Case 2: num is not greater than all elements. The binary search finds an index i where tails[i] is the smallest element greater than or equal to num. We replace tails[i] with num. This does not change the LIS length, but it gives us a new increasing subsequence of length i+1 with a smaller tail. A smaller tail increases our chances of finding longer subsequences later.

After iterating through all numbers, the final length of the LIS is simply the size of the tails list.

Important: The tails list itself is not the LIS. It is a clever auxiliary structure used to efficiently track the length.

Let's watch a video that explains this "patient sorting" analogy and walks through the Java code. The explanation of how to use Collections.binarySearch is particularly helpful.

Implementation Details

As the video explained, Collections.binarySearch in Java has a specific behavior when an element is not found. It returns -(insertion point) - 1. Your task is to transform this negative value back into the correct index where the element should be inserted to maintain order.

index = -(index + 1)

This optimized approach brings the time complexity down to O(n log n) because for each of the n elements, we perform a binary search which takes O(log n) time. The space complexity remains O(n) for the tails list.

Conclusion

Excellent work! You've now added another significant DP problem to your toolkit and, more importantly, learned a powerful optimization technique. The jump from O(n²) to O(n log n) by replacing a linear scan with a binary search is a pattern that appears in several other problems.

Key Takeaways:

• O(n²) Approach:
  • DP State: dp[i] = length of LIS ending at index i.
  • Recurrence: dp[i] = 1 + max(dp[j]) for valid j < i.
  • The final answer is the max value in the dp array.
• O(n log n) Approach:
  • Maintains a sorted tails list where tails[i] is the smallest end element of an increasing subsequence of length i+1.
  • Uses binary search to find the correct position for each number in O(log n).
  • The final answer is the size of the tails list.
• Understanding the trade-offs: The O(n²) solution is often more intuitive to code initially, but the O(n log n) version is far more efficient and necessary for performance-critical scenarios.

Preview of the Next Lesson:
We will continue with dynamic programming by exploring the Matrix Chain Multiplication problem. This problem has a different flavor from the subsequence problems we've seen. It involves finding the most efficient way to parenthesize a sequence of matrix multiplications, and it will introduce you to a common DP pattern used for interval or bracketing problems.