Saturday, July 30, 2016

DP - Longest increasing subsequence

The problem

Given a sequence of numbers S1,S2...,Sn
We have to find a sub-sequence

R1,R2...Rn

such that

R1<R2<...<Rn


The solution

First we create a table by scanning the number from start to end. For each number we find number with largest sequence that is smaller than the current number. We set length of current items sequence length to be one more the found number. We also set the predecessor of the current item to be the found numbers index.
01234567891011
Sequence613284957121611
Length112233445676
Predecessor-1-11122457898
From the table we see that the maximum length is 7 at index 10. So we start at index 10 which will be last item of the sub-sequence. The value is 16. Then we find its predecessor from the predecessor list at index 10 - which is 9. So the next to last item will be item at index 9 which is 12. Which has predecessor at index 7 and so on.
The longest increasing sub-sequence is:
1, 3, 4, 5, 7, 12, 16

Here is the code in python:

 

[This is incomplete but I may not complete it]

1 comment:

  1. Hi vaia, would you also cover O(n log n) solution? Thanks.

    ReplyDelete