Given n numbers, find the longest strictly increasing subsequence (elements in their original order, not necessarily adjacent) — e.g. the longest run of improving results in a training log.
Write LongestIncreasing with dynamic programming: best[i] = length of the longest increasing subsequence that ends at a[i] = 1 + the largest best[j] over all j < i with a[j] < a[i] (take the first such j on a tie, and the first i with the largest best). Keep a previous[] array to rebuild one subsequence.
For the input
8
10 9 2 5 3 7 101 18
the program prints
best[]: [1, 1, 1, 2, 2, 3, 4, 4]
Longest increasing subsequence: 4
One of them: [2, 5, 7, 101]