Given an array, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.
DSA Animator › DSA Revision › Dynamic Programming › Longest Increasing Subsequence
Remember: define dp as the best answer ending at i. The final answer is the maximum over all i, not dp of the last index. The video solves Longest Increasing Subsequence (LeetCode 300, Medium) with the 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Longest Increasing Subsequence animation.
Given an array, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.
For 10, 9, 2, 5, 3, 7, 101, 18, the answer is 4. One such subsequence is 2, 3, 7, 101.
There are 2 to the power n subsequences, so checking all of them is hopeless. Instead, remember the best answer that ends at each position.
Let dp of i be the length of the longest increasing subsequence that ends exactly at index i. Every element alone is a subsequence of length 1. For each earlier index j with a smaller value, you can extend that subsequence by the element at i. So dp of i is 1 plus the largest such dp of j. The answer is the largest value anywhere in dp.
10, 9 and 2 have nothing smaller before them, so they stay at 1. 5 can follow 2, so dp is 2, and 3 can also follow 2, so dp is 2. 7 can follow 5 or 3, both with length 2, so dp is 3. 101 can follow 7, so dp is 4. 18 can also follow 7, so dp is 4. The largest value is 4.
In code, fill dp with 1. For each i, loop over every j before it. If the value at j is smaller, set dp of i to the larger of dp of i and dp of j plus 1. Track the maximum, which takes O of n squared time. A patience sorting method with binary search brings it to O of n log n.
Remember: define dp as the best answer ending at i. The final answer is the maximum over all i, not dp of the last index.