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

ReplyDelete