A[1] A[2]
5 3 opt[1]=1 opt[2]=1 —
A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
7 4 9 2 11 8 13 10 opt[3]=2 opt[4]=2 opt[5]=3 opt[6]=1 opt[7]=4 opt[8]=3 opt[9]=5 opt[10]=4 ¦Ð[3]=2 ¦Ð[4]=2 ¦Ð[5]=3 – ¦Ð[7]=5 ¦Ð[8]=3 ¦Ð[9]=7 ¦Ð[10]=5
(or 1)
(or 4) (or 8)
Longest increasing sequence containing the last element for: A[1] is just 5;
A[1..2] is just 3, because 3 cannot extend 5 (3<5);
A[1..3] is either (3,7) or (5,7) because 7>3 and 7>5;
A[1..4] is (3,4) because 4 can extend only sequence for 3
A[1..5] is (3,7,9) because 9>7 so 9 can extend (3,7);
A[1..6] is just 2 because 2 cannot extend any of the previous sequences; A[1..7] is (3,7,9,11) because 11 can extend (3,7,9);
A[1..8] is (2,7,8) because 8 can only extend (2,7);
A[1..9] is (3,7,9,11,13) because 13 can extend all previous maximal increasing sequences, but the longest is (3,7,9,11)
A[1..10] is (3,7,9,10) or (3,7,8,10)
Optimal solution is opt(9)=5 for achieved for i=9. So the sequence is:
A[2] A[3] A[5] A[7] A[9] 3 7 9 11 13