この問題では直感的に可能な限り大きい区間を選んで、雪かきをしたいです。

より具体的に考えると、\(A_i>A_{i-1}\) となっているのであれば、区画 \(i-1\) で雪かきをするときは常に区画 \(i\) も雪かきしたほうがより多くの雪が一度に減らせます。そして、区画 \(i-1\) と一緒に区画 \(i\) も雪かきするような操作をすべて行うと区画 \(i\) にはまだ \(A_i-A_{i-1}\) の雪が残っています。この分は区画 \(i-1\) と一緒に雪かきすることができないので、新たに\(A_i-A_{i-1}\) 回分雪かきをする必要があります。

逆に、\(A_i<A_{i-1}\) のときは、\(A_{i-1}\) で雪かきするときの一部で一緒に区画 \(i\) を雪かきすると、区画 \(i\) は雪がなくなります。

つまり、\(A\) の前の項との差が正のときはその分だけ新たに答えに加算しているというような形になっています。式にすると

\[ A_1 + \sum_{i=2}^{N} \max(0, A_{i}-A_{i-1}) \]

が答えになります。

これは時間計算量 \(\mathrm{O}(N)\) で計算できます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& e : a) cin >> e;
    int prev = 0;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        if (prev < a[i]) ans += a[i] - prev;
        prev = a[i];
    }
    cout << ans << endl;
}