设 \(f_{i,j}\) 表示从 \(i\) 开始凑出 \(j\) 的连续段的右端点的下一个位置, 初始 \(\forall i\in [1,n], f_{i,a_i}=i+1\), 转移 \(f_{i,j}=f_{f_{i,j-1},j-1}\),和倍增很像。
注意转移时不要让 \(j=a_i\) 否则 \(f_{i,a_i}\) 就变成 \(0\) 了,后面的转移就会出错。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef unsigned long long ll;
int n,a[N],f[N][60];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i],f[i][a[i]]=i+1;int ans=0;for(int j=1;j<=58;j++){for(int i=1;i<=n;i++){if(a[i]!=j)f[i][j]=f[f[i][j-1]][j-1];if(f[i][j])ans=j;}}cout<<ans;return 0;
}