16.3-5 Give an O(n^2) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.

16.3-6 Give an O(n lg n) time algorithm to find the longest monotonically increasing sequence of a sequence of n numbers. (Hint: Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i - 1. Maintain candidate subsequences by linking them through the input sequence.)