increasing subsequence of maximal length?

zpwnchen · #1 $Old$ November 2nd, 2009, 06:18 PM

Quote:

22,5,7,2,23,10,15,21,3,17
a) What is the increasing subsequence of maximal length ?
b) what is the decreasing subsequence of maximal length?

a) i got {5,7,10,15,21} therefore it's 5, but the answer is {7,10,15,21} so it's 4.

b) {22,10,3} therefore it's 3?

Please help me

zpwnchen · #2 $Old$ November 2nd, 2009, 10:02 PM

please someone help me why the answer to a) is 4: {7,10,15,21}

thank you

tonio · #3 $Old$ November 2nd, 2009, 10:05 PM

Quote:

Originally Posted by zpwnchen $View Post$

a) i got {5,7,10,15,21} therefore it's 5, but the answer is {7,10,15,21} so it's 4.

You are right: it's 5.

b) {22,10,3} therefore it's 3?

Yes, it looks fine. There are other descending subsequences of the same length: $\{23,15,3\}\,,\,\,\{23,10,3\}\,,\,\,etc.$

Tonio

Please help me

.

zpwnchen · #4 $Old$ November 2nd, 2009, 10:29 PM

That is prompt reply. Thank you so much!