Longest Increasing Subsequence in O(n²)

For each position, the longest run ending there extends the best earlier run with a smaller value.

The longest increasing subsequence of a sequence is the longest set of its values, kept in their original order, in which each value is larger than the one before. The O(n²) method stores, for each position, the length of the longest increasing subsequence that ends there, found by extending the best earlier one with a smaller value. This card traces that method on eight numbers, then recovers the subsequence itself from a second array of parent positions.

There is one sequence rather than two, so the table has one index: lis[i] is the length of the longest increasing subsequence that ends at position i and uses the value there. A subsequence ending at i is either that value alone, of length 1, or a subsequence ending at some earlier position k with a smaller value, extended by one. So lis[i] is 1 plus the largest lis[k] over every k before i with values[k] < values[i], or 1 if there is no such k. The answer is the largest entry, not the last one, because the longest subsequence need not end at the last value.

The trace below fills lis for 5 2 8 6 3 6 9 7, one position per frame. A dash is an entry not yet computed, and the marker shows the position being filled.

lis[i], the longest increasing subsequence ending at each value of 5 2 8 6 3 6 9 7

Input5 2 8 6 3 6 9 7

5 at 0
1. 1i
2. -
3. -
4. -
5. -
6. -
7. -
8. -
Nothing comes before 5, so the longest increasing subsequence ending at it is 5 alone, of length 1.
2 at 1
1. 1
2. 1i
3. -
4. -
5. -
6. -
7. -
8. -
The only earlier value, 5, is larger than 2, so nothing can come before 2 either: length 1.
8 at 2
1. 1
2. 1
3. 2i
4. -
5. -
6. -
7. -
8. -
Both earlier values are smaller than 8 and each ends a run of 1, so 8 extends one of them to length 2. Its parent is 5, the first one found.
6 at 3
1. 1
2. 1
3. 2
4. 2i
5. -
6. -
7. -
8. -
6 is in the same position as 8: 5 and 2 are smaller, each ends a run of 1, so 6 gets 2.
3 at 4
1. 1
2. 1
3. 2
4. 2
5. 2i
6. -
7. -
8. -
Only 2 is smaller than 3, and 2 ends a run of 1, so 3 gets 2 with 2 as its parent.
6 at 5
1. 1
2. 1
3. 2
4. 2
5. 2
6. 3i
7. -
8. -
5, 2 and 3 are smaller than this 6, and 3 ends a run of 2, so it gets 3. The earlier 6 is equal, not smaller, so it cannot come first.
9 at 6
1. 1
2. 1
3. 2
4. 2
5. 2
6. 3
7. 4i
8. -
Every earlier value is smaller than 9. The 6 at index 5 ends the longest run, 3, so 9 gets 4.
7 at 7
1. 1
2. 1
3. 2
4. 2
5. 2
6. 3
7. 4
8. 4i
9 is larger than 7, so the best predecessor is again the 6 at index 5 and 7 gets 4. The largest entry, 4, first appears at index 6, and following parents back from 9 gives 2 3 6 9.

ResultLength 4, ending at the 9: 2 3 6 9

Every frame looks back at every earlier position, so position i does i comparisons and the whole sequence does 0 + 1 + … + (n − 1), which is about n²/2. The run stored one more array alongside lis: parent[i] is the k that gave position i its length. For this input it was None, None, 0, 0, 1, 4, 5, 5. Starting from the position of the largest entry, 6, and following parents gives the values 9, 6, 3 and 2, which read backwards are 2 3 6 9. Another subsequence of length 4, 2 3 6 7, also exists; the parents record whichever the loop found first.

The comparison is strict, values[k] < values[i], so equal values cannot both appear: the 6 at position 5 does not extend the 6 at position 3. A problem that allows equal neighbours, a longest non-decreasing subsequence, changes the test to ≤.

The cost of the O(n²) method on n values

Time: O(n²), every earlier position checked for every position; every case
Space: O(n) for lis and parent; every case
The answer: The largest entry of lis, wherever it is

On the Algorithms: Design Strategies cheatsheet

← → move through sections and cards