CodeTON Round 5 ( Div1+Div2 ) C. Tenzing and Balls
思路:设f[i]为从 1~i 能删去的最多数
f[i] = max( f[i-1] , i - j + 1+ f[j-1] ) ( a[j]=a[i] , 删去i到j , 再加上前 j-1 可删去的最大数 )
对与 j 可预处理,f[j-1] - j + 1 可根据 a[j] 存一个最大情况
即 ma[a[j]] = max( ma[a[j]] , f[j-1] - j +1 )
f[i] = max( f[i-1] , i + ma[a[i]] )
#define int long long
#define ld long double
using namespace std;
const int INF = -0x3f3f3f3f;
int t;
int f[200010];
int a[200010];
void op()
{
int n;
cin >> n;
vector<int>ma(n + 1,INF);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
f[0] = 0;
for (int i = 1; i <= n; i++)
{
f[i] = max(f[i - 1], i + ma[a[i]]);
ma[a[i]] = max(ma[a[i]], f[i - 1] - i + 1);
}
cout << f[n] << endl;
}
signed main()
{
cin >> t;
while (t--)
{
op();
}
return 0;
}