Can someone please give me some hints to solve this problem. Thanks in Advance!!

If you have time, also tell us why you chose the problems you chose.

Need idea: I thought of finding all possible increasing and decreasing subsequences which is too slow. Can this be done efficiently? Also according to me there can be at max 1 element in common in both the subsequences. I am not getting how to use this information.

This is a beautiful problem that I solved today. The idea is very interesting and the implementation can be a little difficult.