Self-deception

题解

因为Monster是懒狗，所以题解也很水。

首先第一反应肯定是直接暴力，双重循环，能过60，但是想要全过的话，数据范围显然不允许这种事的发生。

观察公式。

我们将要求的$FinalValue$分成两个部分，分别是$value[i] + i$和$value[j]-j$，也就是说，我们只需要分别求出对应的这两个部分的最大值，并且保证$0\le i < j < n$，就可以得到最终的最大值。

题目中说了，所有$value$都会给出。也就是说,对于已经给定的数组，对于特定的$i$和$j$而言，$value[i] + i$和$value[j]-j$值都是确定的。同时注意到$i < j$，所以我们通过一遍遍历，就可以在逐步更新$value[j]-j$的情况下，求出$FinalValue$的最大值。

哦对，注意$value$的范围，不开$long\ long$见祖宗，养成观察数据范围的好习惯。

详见代码。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n;
    ll FinalValue = 0;
    cin >> n;
    vector<ll> values(n);
    for (int i = 0; i < n; i++)
        cin >> values[i];
    ll temp = values[0] + 0;
    // 一遍遍历整个数组
    for (int j = 1; j < n; j++)
    {
        // 更新FianlValue = max(temp + value[j] - j);
        if (FinalValue < temp + values[j] - j)
            FinalValue = temp + values[j] - j;
        // 更新value[i] + i的最大值
        if (temp < values[j] + j)
            temp = values[j] + j;
    }
    cout << FinalValue << endl;
    return 0;
}