LIS with DP

1. Defining the Longest Increasing Subsequence

First, let's be clear about what we're looking for. A subsequence retains the relative order of elements but doesn't require them to be contiguous. An increasing subsequence is a subsequence where each element is strictly greater than the one before it. The LIS is simply the longest one you can find.

For example, given the sequence A = [10, 9, 2, 5, 3, 7, 101, 18]:

• [2, 5, 7, 101] is an increasing subsequence of length 4.
• [2, 3, 7, 18] is another increasing subsequence of length 4.
• [9, 101] is an increasing subsequence of length 2.
• The LIS has a length of 4.

2. The Challenge of Defining the Subproblem

With LCS, our subproblem dp[i][j] naturally depended on two sequences. Here, we only have one. A naive first attempt might be to define LIS(i) as the length of the LIS in the suffix A[i:].

However, this approach quickly runs into a wall. If we compute LIS(i+1), we know the length of the longest increasing subsequence in the rest of the array, but we don't know what value it starts or ends with. Without that information, we can't decide if A[i] can be prepended to it. This lack of information breaks the optimal substructure property.

3. The Correct DP Formulation

As the video highlights, the solution is to add a constraint to our subproblem. The standard and most intuitive way to do this for a bottom-up implementation is to define dp[i] as the length of the longest increasing subsequence that ends at index i.

With this definition, to compute dp[i], we can look at all previous indices j < i. If A[i] > A[j], it means we can potentially extend the LIS that ended at j. We would form a new LIS of length dp[j] + 1 ending at i. Since we want the longest such subsequence, we look at all valid j's and take the one that gives the maximum length.

This gives us the recurrence relation:

If no such j exists (i.e., A[i] is smaller than all preceding elements), the LIS ending at i is just the element A[i] itself, so its length is 1. We can consider the max over an empty set to be 0, simplifying the formula.

Important Note: The final answer is not dp[n-1]. Since the LIS can end at any index, the answer is the maximum value in the entire dp array: max(dp[0], dp[1], ..., dp[n-1]).

Visualizing LIS as a Graph Problem

Another powerful way to conceptualize this problem, which your background in engineering and software might make appealing, is to view it as finding the longest path in a Directed Acyclic Graph (DAG).

• Each number in the sequence is a node.
• A directed edge exists from node A[i] to A[j] if i < j and A[i] < A[j].

The LIS problem is now equivalent to finding the longest path in this DAG. The DP approach we're using is, in fact, a way to compute this longest path.

4. Tabulation Walkthrough and Implementation

Let's see this in action. We'll create a dp array of the same size as our input array and initialize all its values to 1 (since any single element is an LIS of length 1). Then, we iterate through the array, applying our recurrence.

For a more formal and textual representation of the algorithm, the following resource provides clear pseudocode.

5. Complexity Analysis and Reconstructing the Sequence

Complexity

• Time Complexity: $O(n^2)$. We have a nested loop structure. The outer loop runs n times (for i from 0 to n-1), and the inner loop runs i times (for j from 0 to i-1). This gives us a quadratic number of comparisons.
• Space Complexity: $O(n)$. We need an auxiliary array dp of size n to store the lengths of the subproblems.

Reconstructing the LIS

Similar to the LCS and Knapsack problems, our dp table contains enough information to find the length, but to get the actual sequence, we need to store the "path" we took. We can do this by maintaining a predecessor array. When we update dp[i] using dp[j], we set predecessor[i] = j.

Once the dp array is filled, we find the index max_idx where the maximum dp value occurs. This is the last element of our LIS. We can then backtrack from max_idx using our predecessor array to reconstruct the full sequence.

Conclusion

Excellent work today. You've now solved the Longest Increasing Subsequence problem, a classic DP challenge that requires a more nuanced subproblem definition than what we've seen before. Understanding how to define dp[i] as the LIS ending at that position is a key takeaway.

Key Takeaways:

• The LIS problem requires a subproblem definition with a constraint: dp[i] is the length of the LIS ending at index i.
• The recurrence relation is dp[i] = 1 + max({dp[j]}) for all j < i where A[j] < A[i].
• The final answer is the maximum value in the dp array, not necessarily the last element.
• The algorithm has an $O(n^2)$ time complexity and $O(n)$ space complexity.
• The actual subsequence can be reconstructed by storing predecessors and backtracking from the index of the maximum dp value.

Preview of the Next Lesson:
We will continue our journey through sequence-based DP by looking at the Edit Distance (or Levenshtein Distance) problem. This will feel like a return to the structure of LCS, as it involves comparing two strings, but we'll be measuring their difference by counting insertions, deletions, and substitutions. It's a fundamental algorithm in natural language processing and computational biology.