A subsequence keeps the order but may skip values. For each position i, work out the longest increasing run that ends exactly at v[i]: one more than the best run ending at an earlier, smaller value. The answer is the largest of these, and prev pointers recover the values.
- Average time
- O(n²)
- Space
- O(n)