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:

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.

Unfortunately, this approach gives WA. I'd be grateful if anyone could share an $$$\mathcal{O}(N^3)$$$ or an intuitively more convincing $$$\mathcal{O}(N^4)$$$ solution as I was not able to follow the editorial completely.

## include <bits/stdc++.h>

using namespace std; int n;int a[1005]; int solve(int i,int samcnt,int prev){ if(i==n)return samcnt*samcnt; if(i==0){ return solve(i+1,1,a[i]); } else if(prev==a[i]){ return solve(i+1,samcnt+1,a[i]); } else { int op1=1+solve(i+1,samcnt,prev); int op2=samcnt*samcnt+solve(i+1,1,a[i]); return max(op1,op2); } }

int main() { cin>>n; for(int i=0;i<n;i++)cin>>a[i]; cout<<solve(0,0,0); return 0; } I came up with the above recurrence relation! It's working correctly but i don't know how to memoise it! I think using map is a good choice but i don't know how to memoise using map! plz tell me if this relation is correct and send memoised code!

I thought you can only pick consecutive plates, i.e. those that form a subarray. how does $$$kth$$$ occurence of $$$A[i]$$$ work in that case.

Yes say the subarray looks like this

A....A.......A...A Now if we want to take all the A's together in one shot then we'll first have to make them consecutive as you said, so we first remove all the elements which occur between any 2 occurences and then take all K occurences together

It can be solved in $$$O(n^3)$$$. Here is a good editorial

oh wait I can't read