C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

贪心

$从前往后遍历，只要后一天比前一天价格高，那么我们就加上其差值$

$\color{red}{简单证明：}$

$1、可以把数组大致分为(a_{t1}, a_{t1 + 1}), (a_{t2}, a_{t2 + 1}) ···(a_{tk}, a_{tk + 1})$

$2、那么我们最后要想取得最大利润，必然是这一段段区间的差值为正的和$

$时间复杂度：O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int p[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> p[i];

    int res = 0;
    for (int i = 0; i < n - 1; i ++) {
        int dt = p[i + 1] - p[i];
        if (dt > 0)
            res += dt;
    }

    cout << res;

    return 0;
}