I spent a lot of time on this problem.
For those who want to fit the time limit I recommend reading A. Brandstƒadt, D. Kratsch "On partitions of permutations into increasing and decreasing subsequences".
Also M.D. Atkinson "Permutations which are the union of an increasing and a decreasing subsequence" is very interesting to read but not so helpful for this particular problem.

My algo is O(N) DP which does not rely on input array being a permutation. Input can be anything - even floats or strings and may have repeating elements. Moreover, it's "online" DP, so if you don't need detailed result (just 'Possible' or 'Fail') it can be coded in O(1) memory.