题目描述

取石子，满足下标之差 $x$ - $y$ 等于石子价值之差 $a_x$ - $a_y$

思路

题目要求 $a_x$ - $a_y$ = $x$ - $y$
其实也就是转换为 $x$ - $a_x$ = $y$ - $a_y$
因此我们只需遍历一次，将下标与石子价值的差作为hash map的键

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<int,long long> mp;
    int n;
    long long res=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int a;
        cin>>a;
        mp[i-a]+=a;
        res=max(res,mp[i-a]);
    }
    cout<<res;
}