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.