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.

	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

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:

def create_predecessor_table(seq): n = len(seq) lengths = [0] * n predecessor = [-1] * n for i in range(n): for j in range(i): if seq[i] > seq[j] and lengths[i] < lengths[j]: lengths[i] = lengths[j] predecessor[i] = j lengths[i] += 1 return predecessor, lengths def generate_sub_sequence(seq, idx, predecessor): sub_seq = [] while idx != -1: sub_seq = [seq[idx]] + sub_seq idx = predecessor[idx] return seq sequence = [6, 1, 3, 2, 8, 4, 9, 5, 7, 12, 16, 11] preds, lens = create_predecessor_table(sequence) maxidx = lens.index(max(lens)) lis = generate_sub_sequence(sequence, maxidx, preds) print(sequence) print(preds) print(lens) print(lis)

[This is incomplete but I may not complete it]