Given an array A of lower case characters $$$a_1,a_2,....,a_n$$$ we need to perform the following operation until it becomes empty,
Select a segment $$$(l,r)$$$ such that $$$a_l=a_{l+1}=a_{l+2}=....=a_r$$$ and remove the segment from the array.
Add the square of length of segment to your score and rearrange the remaining elements.
Output the maximum score that can be obtained.(score is initialized to 0).
Constraints: n <= 60
input
2
6
a a b b a c
12
a b a b a b a b a b a b
output
14
42
Hi bro
My Hint
Dynamic programming?
Hint2
sub-segments
It can be solved using Dynamic Programming by maintaining 2 states(l,r)
If there's only one element (l == r), then dp[l][r] = 1
If the segment A[l:r+1] consists of identical characters (A[l] == A[r] for all l <= i <= r), remove it as a whole to get dp[l][r] = (r-l+1)^2
For any two indices k where l <= k < r, split the segment A[l:r+1] into A[l:k] and A[k+1:r], and maximize the score by combining scores from these subarrays.
The complexity using this can go till O(n^3) which works for N <= 100
I don't think this would work can you explain the subparts for the 2nd case which would lead to answer 42.
wouldn't this break if
aaaaaaaaabaaaaaaaaaaa
obvious answer is to break the b and get 401
if you did dp then dp[l][r] it would only get 203 i think
Yea that's what I was trying to say, dp[l][r] doesn't work so is there any other way or idea of solving the above problem?
$$$\mathrm{dp}[l][r]$$$ should still work, just the calculation is a bit more involved.
Say we want to calculate $$$\mathrm{dp}[l][r]$$$. In addition to the obvious cases of $$$A[l] = \cdots = A[r]$$$ and $$$\mathrm{dp}[l][m] + \mathrm{dp}[m + 1][r]$$$, do something like this if $$$A[l] = A[r]$$$.
Let's make a new array $$$\mathrm{xdp}[i][j]$$$, initialize it to $$$-\infty$$$ initially. Roughly, $$$\mathrm{xdp}[i][j]$$$ represents the maximum score we can get if we remove $$$j$$$ items among the first $$$i$$$ with the current operation (other items have already been removed with previous steps). Set $$$\mathrm{xdp}[l][1] = 0$$$. For each $$$i$$$, $$$l < i \le r$$$:
To calculate $$$\mathrm{dp}[l][r]$$$ from this data, take the maximum of $$$\mathrm{xdp}[r][j] + j^2$$$ over all $$$j$$$.
Complexity should be $$$O(n^5)$$$. This sounds a bit too slow for $$$n \le 60$$$, but it has a very good constant: for given $$$l, r$$$, we only need to look at $$$i, L \in [l, r]$$$ and $$$j \le r - l + 1$$$. So it's really more like $$$\frac{n^5}{20}$$$ maximums and additions.