Define as the length of the longest increasing subsequence ending at index . Why "ending at " instead of "using elements 0 to "? Because when we extend a subsequence, we need to know its last element.
If just meant "best in prefix", we wouldn't know what value to compare against. With the "ending at" definition, is the last element. We can check if for all and extend from there. Base case: for all . Every element by itself is a valid increasing subsequence.