452. Longest Increasing Subsequence
Given n integers, print the length of the longest strictly increasing
subsequence.
A subsequence keeps the original order but may skip elements, so it does not
have to be contiguous. In 10 9 2 5 3 7 101 18 one longest increasing
subsequence is 2 3 7 18, of length 4.
The state must be "the longest chain ending exactly at index i". Defining it as "the longest chain within the first i elements" looks equivalent and is not: it does not record what the chain ended on, so you cannot tell whether the next element may follow it.
Constraints - `1 ≤ n ≤ 2500` - `-1000000 ≤ a[i] ≤ 1000000` - A quadratic solution is fast enough.
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer: the length of the longest strictly increasing subsequence.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.