能用递归做的题为什么要想差分。。。

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int INF = 10001;
vector<int> a;
int n, ans = 0;


void build(int l, int r)
{
    if (l == r - 1)
    {
        ans += a[l];
        return;
    }
    else if (l == r)
        return;
    int start = l, minx = INF;
    for (int i = l; i < r; i++)
        minx = min(a[i], minx);
    ans += minx;
    for (int i = l; i < r; i++)
    {
        a[i] -= minx;
        if (a[i] <= 0)
        {
            build(start, i);
            start = i + 1;
        }
    }
    build(start, r);
}

int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n ; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    build(0, n);
    cout << ans;
    return 0;
}