Longest Increasing Subsequence

Let's trace the dynamic programming solution for the sequence: 1, 3, 2, 4.

Experiment: Interactive DP Trace

You can reproduce this algorithm in the Longest Increasing Subsequence module:

1. Type 1,3,2,4 into the Sequence control.
2. Click the Step control to reveal the DP computation for each index one by one.
3. Observe that at the final step, the chosen witness tuple is [0,1,3] instead of [0,2,3] due to the lexicographical index tie-breaker.
4. Click Finish to show all remaining rows immediately. Then click the Reset control to rewind and start over.