The problemGiven a sequence of numbers S1,S2...,Sn
We have to find a sub-sequence
The solutionFirst 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.
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]