DP思路证明
a[i] 表示输入数组
b[i] 表示以 a[i] 结尾的最长连续不重复子序列 (代码中使用 a[i] 自更新)
则 ans = max(b[0], b[1], ……, b[n-1])
如何求b[i]
p[i] 表示 a[i] 在 i 之前中出现的位置
情况1:p[i] 在 b[i-1] 所包含的子序列之前 (p[x] < i - b[i-1]),则b[i] = b[i-1] + 1
情况2:出现在之后,则 b[i] 更新为 p[i] 下一位到 i 的长度
Lucas
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int a[N], p[N], n, ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
for (int i=1; i<=n; i++) {
int x=a[i];
if (p[x]<i-a[i-1]) a[i]=a[i-1]+1;
else a[i]=i-p[x];
p[x]=i;
ans = max(a[i], ans);
}
cout<<ans<<endl;
return 0;
}