O(n) 做法警示后人
查看原帖
O(n) 做法警示后人
1161172
HaneDaniko楼主2024/11/20 18:14

核心代码部分

for(int i=1;i<=n;++i){
    f[i]=f[i-1];
    if(last[a[i]]) f[i]=max(f[i],f[last[a[i]]+1]+sum[i]-sum[last[a[i]]+1]+a[i]);
    last[a[i]]=i;
}

这里的 last[a[i]]+1 有可能等于 i,因此你要先把 i 更新成 f[i-1]

2024/11/20 18:14
加载中...