Longest Increasing Subsequence
You've learned prefix sums. Now find the longest increasing subsequence and optimize with binary search.
Lessons
1. Intro
The Goal
2. Vocabulary - Subsequence
The definition
3. LeetCode 300 Longest Increasing Subsequence - Problem Statement
Classic DP problem
4. LeetCode 300 Longest Increasing Subsequence - Why Greedy Fails
The trap
5. LeetCode 300 Longest Increasing Subsequence - State Design
What dp[i] means
6. LeetCode 300 Longest Increasing Subsequence - Transition
The recurrence
7. LeetCode 300 Longest Increasing Subsequence - Implementation
The code
8. LeetCode 300 Longest Increasing Subsequence - Walkthrough
Tracing the O(n^2) algorithm
9. Challenge: LIS Reconstruction
Finding the actual subsequence
10. Quiz: LIS State Design
Why ending at i
11. Quiz: LIS Basics
Knowledge check
12. Lessons from LIS
summary
13. LeetCode 300 Longest Increasing Subsequence - Binary Search Optimization
The optimization idea
14. LeetCode 300 Longest Increasing Subsequence - Binary Search Implementation
O(n log n) code
15. LeetCode 300 Longest Increasing Subsequence - Binary Search Walkthrough
O(n log n) algorithm trace
16. Why Binary Search Works
Understanding the tails array
17. Quiz: LIS Optimization
Knowledge check
18. LeetCode 673 Number of Longest Increasing Subsequences - Problem Statement
Counting all LIS
19. LeetCode 673 Number of Longest Increasing Subsequences - Dual State
Length and count
20. LeetCode 673 Number of Longest Increasing Subsequences - Implementation
The code
21. LeetCode 673 Number of Longest Increasing Subsequences - Walkthrough
Counting subsequences
22. Quiz: Counting LIS
When counts add up
23. LeetCode 354 Russian Doll Envelopes - Problem Statement
2D LIS variant
24. LeetCode 354 Russian Doll Envelopes - Walkthrough
2D LIS reduction
25. LeetCode 1048 Longest String Chain - Problem Statement
LIS on string predecessors
26. LeetCode 1048 Longest String Chain - Walkthrough
LIS on strings
27. LeetCode 368 Largest Divisible Subset - Problem Statement
LIS with divisibility
28. LeetCode 368 Largest Divisible Subset - The LIS Connection
Hidden pattern
29. LeetCode 368 Largest Divisible Subset - Implementation
The code
30. LeetCode 368 Largest Divisible Subset - Walkthrough
LIS with divisibility
31. Quiz: LIS Variants
Recognizing the pattern
32. Maximum Sum Increasing Subsequence - Problem Statement
Classic variation
33. Maximum Sum Increasing Subsequence - State Change
Sum instead of length
34. Maximum Sum Increasing Subsequence - Implementation
The code
35. Maximum Sum Increasing Subsequence - Walkthrough
Weighted LIS
36. Challenge: Max Sum IS Reconstruction
Finding the optimal subsequence
37. Longest Bitonic Subsequence - Problem Statement
Bidirectional LIS
38. Longest Bitonic Subsequence - Two Passes
Forward and backward
39. Longest Bitonic Subsequence - Implementation
The code
40. Longest Bitonic Subsequence - Walkthrough
Two-directional LIS
41. Quiz: Bitonic Structure
Understanding the approach
42. Minimum Deletions for Sorted - Problem Statement
LIS application
43. Minimum Deletions for Sorted - Implementation
LIS for non-decreasing
44. Pattern - LIS Family
Recognizing LIS problems
45. Challenge: LIS in O(n log n) Space O(n)
Understanding space usage
46. What's Next
Preview of LCS and Edit Distance
47. Section Recap
What we learned
Practice Problems
The classic two-string DP that shows up everywhere. Foundation for edit distance, diff tools, and sequence alignment.
LCS plus a third operation. Powers spell checkers and translation scoring. Teaches multiple transitions from the same state.
Shifts from "find the best" to "count all ways." When chars match, you add paths instead of taking max. Classic interview problem.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Covered with full walkthrough in this section.
Construct sequences with min/max LIS given constraints. Tests deep understanding of LIS structure.
Maximize min(LIS, reverse LIS) through rearrangement. Beautiful observation about LIS symmetry.
LIS of array concatenated n times. Elegant reduction to counting distinct elements.
Classify elements by their role in all LIS. Advanced understanding of LIS uniqueness.
XOR of LIS lengths across subarrays. Parity observation makes complex problem simple.
LIS with bounded gaps using segment tree. Advanced data structure optimization of LIS.
LIS where adjacent elements share a prime factor. Combines number theory with LIS.
Find max independent set in bubble sort graph. Reduces to LIS via inversions.
Find longest subsequence of consecutive integers. LIS variant with value tracking.
Partition array into three sorted parts. LIS ideas with multiple segments.
Find cities reachable from all but one. DAG + LIS-style reachability.
Represent number as sum of k distinct remainders. Number theory + construction.
LIS with values - maximize sum of beauties in increasing height subsequence. Segment tree optimization.