Longest increasing subsequence

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution.

For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5. How to arrive at this in O(n log n) ?

The O(nlogn) algorithm works as follows:
Let the array be A[1...n] i.e elements are A[1], A[2], .. , A[n], assume all are distinct.
Idea is to maintain for each k, the smallest element A[ik] such that the maximum length monotone subsequence that ends at A[ik] is of length k.

Lets walk through the solution.

1. Start off with A[1] = 1. For this array we get i1 = 1. Now add A[2]=8 to the list.
• Since A[2]>A[1], we get i2=2. Now the list contains [1,8]
2. Try adding A[3]=2 to the list.
• Since 1<2<8, we set i2=3. List now has [1,2]
3. Try adding A[4]=7 to the list.
• Since 7>2, we set i3=4. List now has [1,2,7]
4. Try adding A[5]=3 to the list.
• Since 2<3<7, we set i3=5. List now has [1,2,3]
5. Try adding A[6]=6 to the list.
• Since 6>3, we set i4=6. List now has [1,2,3,6]
6. Try adding A[7]=4 to the list.
• Since 3<4<6, we set i4=7. List now has [1,2,3,4]
7. Try adding A[8]=5 to the list.
• Since 5>4, we set i5=8. List now has [1,2,3,4,5]

Note that in this case walking the tree gave you the right sequence, but that need not be true for all sequences. The algorithm I gave gives the length of the longest sequence, you will have to modify it to get the exact sequence.

Advertisement