The basic table
The longest increasing subsequence is the longest subsequence whose values strictly increase. The straightforward DP defines dp at i as the length of the best increasing subsequence ending at index i. For each i, look at all earlier j with a smaller value and take the best, then add one.
The faster method
A smarter approach keeps a list of the smallest possible tail for an increasing subsequence of each length. For each new value, find the first tail that is not smaller and replace it, or append if the value exceeds every tail.
- The tails list stays sorted, so the search uses binary search.
- The length of the tails list equals the current best subsequence length.
The tails list is not an actual subsequence, but its length is exactly the answer, which is the elegant trick of this method.
Key idea
LIS can use a per index table that scans all earlier smaller elements, or a sorted tails list updated by binary search whose length is the answer, trading clarity for speed.