Longest Increasing Subsequence
Find the length of the longest strictly increasing subsequence.
Why does this pattern fit?
Restate the exact job
Find the length of the longest strictly increasing subsequence.
The smallest possible tail for each length leaves maximum room to extend.
O(n log n) time · O(n) space
Tails is not necessarily an actual subsequence; only its length is the answer.
How to solve Longest Increasing Subsequence
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Find the length of the longest strictly increasing subsequence.
Why Dynamic programming fits
The smallest possible tail for each length leaves maximum room to extend.
State to maintain
An ordered tails array where tails[i] is the minimum tail for length i+1.
Transition
Binary-search the first tail ≥ value and replace it, or append if none.
Time and space
O(n log n) time · O(n) space
Counterexample to the tempting mistake
Tails is not necessarily an actual subsequence; only its length is the answer.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.