Longest Increasing Subsequence

Worked Example: Finding the Longest Increasing Subsequence

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

1. i=0, value=1: LIS is 1 itself. L[0]=1, path=[0].
2. i=1, value=3: 1 < 3, so L[1] = L[0] + 1 = 2, path=[0, 1].
3. i=2, value=2: 1 < 2, so L[2] = L[0] + 1 = 2, path=[0, 2].
4. i=3, value=4: 1 < 4 (L=2), 3 < 4 (L=3), 2 < 4 (L=3). Both predecessors j=1 and j=2 yield a length of 3. We break the tie by choosing the lexicographically smallest index tuple. The paths are [0, 1, 3] and [0, 2, 3]. Since 1 < 2, we select [0, 1, 3]. L[3]=3, path=[0, 1, 3].

The longest increasing subsequence has length 3, with indices [0, 1, 3] and values [1, 3, 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.

Limitations of the O(n²) Approach

The recurrence examines O(n²) predecessor pairs. This bounded implementation also copies and compares explicit witness tuples, so it does not promise O(n²) end-to-end running time. Faster O(n log n) length algorithms use binary search with appropriate reconstruction bookkeeping. The input is limited to 12 integers from -9 through 9, inclusive. Empty input has length 0; invalid tokens hide results.

References and Further Reading

The recurrence relation and O(n²) dynamic programming algorithm are detailed in the lectures of the course "CS 375: Design and Analysis of Algorithms". The algorithm requires computing lengths of longest increasing subsequences ending at each element. See the lecture Longest Increasing Subsequence for more details on the recurrence, optimal substructure property, and running time.