Longest Monotonically Increasing Subsequence
Today, let’s take a look at another interesting exercise given in the CLRS book [1]. Problem Statement Exercise 15.4-6 Give an $O(n \cdot log_2 n)-$ time algorithm to find the longest monotonically increasing subsequence 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.) Longest Monotonically Increasing Subsequence - Approach There may be many different approaches to solve this problem. However, we are going to describe one such approach that we came up with. Each approach has its own strengths and weaknesses. The book [1] suggests a different approach to what we are going to present here. Nonetheless, both the approaches have the same asymptotic time and space complexity. Our approach uses an auxiliary array $m$ to store intermediate results. Finally, this array shou