I am trying to solve the problem BAT2 on spoj . Click here to see the question. Here's my idea :

x1 = Length of longest increasing subsequence . x2 = Length of longest decreasing subsequence .

Note that the longest increasing subsequence and the longest decreasing subsequence can have at most one common element. Consider all the longest increasing subsequences and all the longest decreasing subsequences. If we are able to find an increasing subsequence and a decreasing subsequence so that they don't have a common element our answer is x1+x2 else our answer is x1+x2-1 .

Now the problem is find whether or not such a pair of longest increasing subsequence and a pair of longest decreasing subsequence exists or not. How to do so efficiently?