D — Almost Triple Deletions
Author: Gheal
Hints
Hint 1
Consider the opposite problem: What is the smallest possible length of a final array?
Hint 2
For which arrays is the smallest possible final length equal to $$$0$$$?
Hint 3
Considering the second hint, it is possible to completely remove some subsequences from the array.
Solution
Lemma: An array $$$a_1,a_2,\ldots, a_n$$$ can be fully deleted via a sequence of operations if and only if it satisfies both of the following constraints:
$$$n$$$ is even
The maximum frequency of any element in the array is at most $$$\frac n2$$$.
Proof
If $$$n$$$ is odd, then any final array will also have an odd length, which can't be $$$0$$$.
An optimal strategy is to always delete one of the most frequent elements and any one of its neighbours. If the most frequent element occurs $$$k \gt \frac n2$$$ times, then the final array will have at least $$$n-2 \cdot (n-k)=2\cdot k - n \gt 0$$$ elements. Otherwise, this strategy ensures the full deletion of the array, since, after performing an operation, it is impossible for an element to occur more than $$$\frac {n-2}{2}$$$ times in the array.
Since the maximum frequency of a value for every subsequence $$$[a_l,a_{l+1},\ldots,a_r]$$$ can be computed in $$$O(n^2)$$$, it is possible to precompute all subsequences which can be deleted via a sequence of operations.
Let $$$dp[i]$$$ be the maximum length of a final array consisting of $$$a_i$$$ and some subarray from the first $$$i-1$$$ elements. Initially, $$$dp[i]$$$ is set to $$$1$$$ if the prefix $$$[a_1,a_2,\ldots, a_{i-1}]$$$ can be fully deleted. Otherwise, $$$dp[i]=0$$$.
For every pair of indices $$$i$$$ and $$$j$$$ ($$$1 \le j \lt i \le n, a_i=a_j$$$), if we can fully delete the subsequence $$$[a_{j+1},a_{j+2},\ldots a_{i-1}]$$$, then we can append $$$a_i$$$ to any final array ending in $$$a_j$$$. Naturally, $$$dp[i]$$$ will be strictly greater than $$$dp[j]$$$. This gives us the following recurrence:
$$$dp[i]=\max_{j=1}^{i-1}(dp[j]>0 \text{ and } a_i=a_j \text{ and } [a_{j+1},a_{j+2},\ldots,a_{i-1}] \text{ is deletable}) \cdot (dp[j]+1)$$$
If we define a final array as a subarray of equal elements from the array $$$a$$$, to which $$$a_{n+1}$$$ is forcefully appended, then the final answer can be written as $$$dp[n+1]-1$$$. Note that, when computing $$$dp[n+1]$$$, $$$a_j$$$ should not be compared to $$$a_{n+1}$$$.
Total time complexity per testcase: $$$O(n^2)$$$.