Hey, I have found this interesting problem on Timus judge. Here's a link to the problem : 1221. Malevich Strikes Back!. Could you please help me as to how to proceed on this problem.

Thanks in advance.

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?