Microsoft Word – LMS.docx
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
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]
5 3 7 4 9 2 11 8 13 10
opt[1]=1 opt[2]=1 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
(or 1)
π[4]=2 π[5]=3 – π[7]=5 π[8]=3
(or 4)
π[9]=7 π[10]=5
(or 8)