关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：模拟 + 哈希

• 对于选好的石子，相邻两个必须满足 $x - y = a_x - a_y$，也即 $a_x - x = a_y - y$。所以，所有满足 $a_x - x = t$ 的石子（$t$ 为定值）均可以被归到一类，作为一种选择方案。所以我们需要用一类数据结构来保存所有不同 $t$ 值对应石子的价值总和，由于这是一组映射关系，所以我们很容易想到利用哈希表来存储。
• 由于最终的 $t = a_i - i$ 组合数值范围仅在 $[1 - 2 \times 10^5, 4 \times 10^5 - 1] = [-199999, 399999]$ 区间，所以我们在读取全部石子后，可以遍历所有可能的 $t$ 值，根据每一个 $t$ 值对应的石子价值总和来更新全局最大值。

代码：（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
typedef vector<int> VI;


int main() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    map<int, ll> mp;

    ll ret = 0;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i] - i] += a[i];
    } 

    for(int i = -200010; i <= 400010; i++) {
        ret = max(ret, mp[i]);
    }

    cout << ret << endl;
}

复杂度分析：

• 时间复杂度为 $O(C)$，其中 $C = 4 \times 10^5$
• 空间复杂度为 $O(n)$