Given array A, determine the maximal possible longest common subsequence over all pairs of longest non-increasing and longest non-decreasing subsequences of A.
Let P and Q be some longest non-increasing and longest non-decreasing subsequences of A respectively.
Claim: The longest common subsequence of P and Q can not contain two different numbers (that is, all terms of the LCS are the same).
Assume the contrary.
Then there exists some a,b\space(a\ne b) in the LCS. WLOG, let a<b.
If a appears before b in the LCS, since the LCS is a subsequence of P, a appears before b in P, a contradiction to the non-increasing property of P.
We can similarly show contradiction for the case where a appears after b.
From the above claim, it is obvious that if the optimal LCS is comprised of integer x, then the number of times x occurs in both P and Q should be maximum (while still being some longest non-increasing and longest non-decreasing subsequence, respectively).
If c_x and d_x represent the maximum number of times x occurs over all P and Q respectively, the answer is then equal to
How do I compute these values?
We only discuss the steps to compute array c, since d can be computed in a similar fashion.
Let I[i] be the length of the longest non-increasing subsequence (from left to right) of A with A_i as it’s last term. Also, let IC[i] be the maximum number of times elements with value A_i can occur in this subsequence.
Similarly, let D[i] be the length of the longest non-decreasing subsequence (from right to left) of A with A_i as it’s last term. Let DC[i] be the maximum number of times elements with value A_i can occur in this subsequence.
Both these arrays can be computed in O(N\log N) each, using a slightly modified version of the longest increasing subsequence algorithm.
Then, the longest non-increasing subsequence that contains A_i has length I[i]+D[i]-1 (the -1 is because element A_i is double counted), and the maximum number of times elements with value A_i can occur is equal to IC[i]+DC[i]-1.
Finally (this step is important, since selecting A_i might not give the longest possible non-increasing subsequence of A), if I[i]+D[i]-1 is equal to the length of the longest non-increasing subsequence of A, update
Calculating array c and d takes amortized O(N\log N), and calculating the answer from this takes O(N), making the total time complexity
per test case.
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)