Hello friends,
I was trying to solve this dynamic programming problem. The editorial proposes an \mathcal{O}(N^4) solution to this problem, but I think it could be solved in \mathcal{O}(N^3) time according to the following approach:
DP[i][j] \rightarrow \text{Max score we can get from subarray }A[i \dots j]
Say, i \le e_k \le j \rightarrow kth occurence of A[i] between i and j, K \rightarrow number of occurrences of A[i] in [i\dots j] .
Transitions are as follows.
\displaystyle DP[i][j]=\max(DP[i+1][j],\sum_{k=1}^{K-1} DP[e_k+1][e_{k+1}-1]+K^2)
Unfortunately, this approach gives WA. I’d be more than grateful if someone could share an \mathcal{O}(N^3) or an intuitively more convincing iterative \mathcal{O}(N^4) solution as I was not able to follow the editorial completely.