实现方法：
1.先二维前缀将每个数字的前缀和保存，再保存他们前缀增加时候的位置（last数组维护）。
2.然后枚举从1~26的左边=右边长度（k 1 k1k1）,然后找到他们前缀有k 1 k1k1个x （ 范 围 1 − 26 ） x（范围1-26）x（范围1−26），后缀有 k 1 k1k1 个x xx的下标，然后中间找最大k 2 k2k2长度，记录最大值即为答案，时间复杂度O ( m ∗ n ) O(m*n)O(m∗n).
3.详情看注解。
/********************************************************************* 程序名: 版权: Joecai 作者: Joecai 日期: 2022-04-11 10:39 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define eb emplace_back #define sp(i) setprecision(i) const int N = 2e5 + 10, INF = 0x3f3f3f3f; void solve() { int n; cin >> n; vector<vector<int>>sum(27, vector<int>(n + 1, 0));//等于sum[26][n],求数字x的前缀和 vector<vector<int>>last(27, vector<int>(n + 2, 0));//等于last[26][n] 保存i前缀和为j时的下标 for (int i = 1; i <= n; i++) { int x; cin >> x; for (int j = 1; j <= 26; j++) sum[j][i] = sum[j][i - 1];//维护前缀和 sum[x][i]++; last[x][sum[x][i]] = i;//更新前缀和对应的下标 } for (int i = 1; i <= 26; i++) { last[i][sum[i][n] + 1] = last[i][sum[i][n]] + 1;//防止越界，设置一下 } int ans = 0; for (int i = 1; i <= 26; i++) { for (int j = 0; j <= sum[i][n]; j++) { int l = last[i][j] + 1; int r = last[i][sum[i][n] - j + 1] - 1; if (l > r) break; for (int k = 1; k <= 26; k++) { int cnt = sum[k][r] - sum[k][l - 1]; ans = max(ans, j * 2 + cnt); } } } cout << ans << endl; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; cin >> __; while (__--) { solve(); } return 0; }
