monotonically increasing subsquence..

Give an o(n^2) time algo to find the longest monotonically increasing subsequence of a sequence of n numbers

Answers:

Check the dynamic programming section on Cormen's book.

its very simple for O(n^2)
can anyone tell me O(n lg n) solution. This is asked in cormen to do in O(n lg n) but i've failed to do so. An algorithm of O(n lg n) is given in dasgupta but i fail to understand how it can actually be implemented in O(n lg n)

O(nlogn)
DP coupled with binary search.
at each stage we get sorted sub-sequence, so for next element just searching(binary) that sequence to find position of that element in sub-sequence would do it.
It is basically O(nlogk) where k is length of longest MIS.