题意 :
给定$a[]$,你需要选出一个序列使得其所选序列不仅满足条件而且和最大
限制条件如下 :
对于所选序列中,所有$i - j =a_i-a_j$
思路 :
首先对于形如这种$i-j=a_i-a_j$都可以化简为$i-a_i=j-a_j$
然后通过一次遍历,每次使用$map$存放$i-a_i$即可
但是这道题需要统计的是,和的最大值
所以一下子我纳闷了,偏到 选取多个等差数列然后求最大值
但是其实这题还是可以使用上面那个通法的
我们对于遍历的$i$设有$mp[i-a[i]]+=a[i]$
这样子就相当于把这个集合加上了$a[i]$,最后查询每个集合即可
最后还是在集合上面操作
map<int,int> mp;
int ans ;
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
mp[x-i] += x;
ans = max(ans,mp[x-i]);
}
cout<<ans<<endl;
}
signed main(){
//int t;cin>>t;while(t--)
solve();
return 0 ;
}