二分 + 递推

时间复杂度：$O(n \times log(n))$

对答案进行二分，可取到满足条件的最小能量值，具体可参考二分模板 二分查找算法模板。

在进行 check 判断时，需要注意容易爆 long long，因为 $N$ 最大可达 $100000$，不断累加二分值，必定会爆 long long（卡死我了），其实如果二分值 $\ge$ $h$ 数组的最大值，就可以完成游戏，此时就不会出现溢出的问题，因为 $h[i]$ 最大只可取到 $100000$。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n, mx = 0;
int h[N];

bool check(LL x)
{
    for (int i = 1; i <= n; ++i) {
        if (h[i] - x > 0) x -= (h[i] - x);
        else x += (x - h[i]);
        if (x >= mx) return true;
        if (x < 0)   return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        mx = max(mx, h[i]);
    }
    LL l = 1, r = 1e5;
    while (l < r) { // 二分的为答案
        LL mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}