The problem
Given a sequence of numbers S1,S2...,SnWe 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.0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
Sequence | 6 | 1 | 3 | 2 | 8 | 4 | 9 | 5 | 7 | 12 | 16 | 11 |
Length | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 6 | 7 | 6 |
Predecessor | -1 | -1 | 1 | 1 | 2 | 2 | 4 | 5 | 7 | 8 | 9 | 8 |
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]
Hi vaia, would you also cover O(n log n) solution? Thanks.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteOur mortgage payment calculator provides you with everything you need to evaluate different scenarios, to assist you decide what mortgage is right to suit your needs. mortgage payment calculator canada Condo owners pay fixed monthly fees that cover costs, such as building insurance and property maintenance, elevators, roofing, fitness facilities and much more. mortgage calculator
ReplyDelete