考虑求出全局的众数 \(A\)。
那么有一个结论，就是答案区间的众数中绝对有 \(A\)。
考虑反证法，如果没有 \(A\)，\(A\) 在序列中出现的个数一定 \(\ge\) 区间内众数的出现个数，所以可以一直往外扩展直到 \(A\) 出现的个数与区间内非 \(A\) 众数的个数持平，这样肯定更优。
于是可以考虑钦定区间的另一个众数为 \(B\)。
那么把 \(a_i = A\) 的看作 \(1\)，\(= B\) 的看作 \(-1\)，其他的看作 \(= 0\)。
那么 \(\sum = 0\) 的区间就说明 \(A, B\) 个数相同，便可以统计进答案。
可以做出前缀和维护每种前缀和最先出现的位置得到答案。
时间复杂度 \(O(nV)\)。
代码
#include<bits/stdc++.h>
const int maxn = 4e5 + 10;
int a[maxn];
int cnt[maxn], L[maxn];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) cnt[a[i]]++;
int A = 1;
for (int i = 1; i <= 100; i++) cnt[i] > cnt[A] && (A = i);
int ans = 0;
memset(L, -1, sizeof(L));
for (int B = 1; B <= 100; B++) {
if (A == B) continue;
int tot = 0; L[n] = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == A) tot++;
else if (a[i] == B) tot--;
if (~ L[tot + n]) ans = std::max(ans, i - L[tot + n]);
else L[tot + n] = i;
}
tot = 0, L[n] = -1;
for (int i = 1; i <= n; i++) {
if (a[i] == A) tot++;
else if (a[i] == B) tot--;
L[tot + n] = -1;
}
}
printf("%d\n", ans);
return 0;
}