给定两个长为 \(n\) 的数组 \(a\) 和 \(b\) 。你需要将 \(a\) \(b\) 归并成一个数组 \(c\) 。询问所有归并方法中,连续数相同的子段最长为多少。\(1 \leq a_i, b_i \leq 2n\) 。
显然归并在 \(a\) 可以任选一段 \([l_1, r_1]\) ,在 \(b\) 任选一段 \([l_2, r_2]\) 。使 $c = \cdots a_{[l_1, r_1]} b_{[l_2, r_2]} \cdots $ 。
于是可以对 \(a\) 和 \(b\) 执行以下操作,开值域数组 \(v\) , \(v_x\) 代表 \(x\) 作为连续数出现的最长长度。
答案为 \(max_{i=1}^n va_i + vb_i\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n; std::cin >> n;
std::vector<int> a(n+1), b(n+1), va(2*n+1), vb(2*n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i];
for (int i = 1; i <= n; i++) std::cin >> b[i];
for (int i = 1; i <= n; i++) {
int j = i;
while (j + 1 <= n && a[j + 1] == a[i]) j++;
va[a[i]] = std::max(va[a[i]], j - i + 1);
i = j;
}
for (int i = 1; i <= n; i++) {
int j = i;
while (j + 1 <= n && b[j + 1] == b[i]) j++;
vb[b[i]] = std::max(vb[b[i]], j - i + 1);
i = j;
}
int ans = 0;
for (int i = 1; i <= 2 * n; i++) ans = std::max(ans, va[i] + vb[i]);
std::cout << ans << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}