### 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.

ReplyDeleteI like the helpful information you provide in your articles. I will bookmark your blog and check again here regularly. I am quite sure I'll learn lots of new stuff right here! Best of luck for the next! facebook login in

ReplyDelete