Algorithms, Vol. 12, Pages 237: What Do a Longest Increasing Subsequence and a Longest Decreasing Subsequence Know about Each Other? (Algorithms)

As a kind of converse of the celebrated Erdos–Szekeres theorem, we present a necessary and sufficient condition for a sequence of length n to contain a longest increasing subsequence and a longest decreasing subsequence of given lengths x and y, respectively.