贪心

参考代码：

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

using namespace std;

const int N = 1e5 + 10;

int n, a[N];

/*
任何跨越大于1天的交易都可以拆解为多个一天的和，会发现中间的买入一次，卖出一次都会被抵消！
因此本题转换为了n - 1段交易，选择不会亏的即可，即该段交易大于0即可！
*/

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int res = 0;
    for(int i = 2; i <= n; i ++) res += max(0, a[i] - a[i - 1]);
    cout << res << endl;
    return 0;
}

状态机模型

参考代码：

注意点：f[0][1]的初始化，会因为股票高价买入，低价卖出跌到亏本，因此初始化为负无穷！

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

using namespace std;

const int N = 1e5 + 10;

int n, w[N], f[N][2];

/*
转态机模型：

状态表示：f[i][j]表示前i天中选择，第i天是否持股的集合中的最大值（0未持有，1持有）
状态计算：
    未持有：f[i][0]
        第i - 1天未持有第i天不操作：f[i - 1][0]
        第i - 1天持有第i天卖出：f[i - 1][1] + w[i]
    持  有：f[i][1]
        第i - 1天未持有第i天买入：f[i - 1][0] - w[i]
        第i - 1天持有第i天不操作：f[i - 1][1]
*/

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> w[i];
    // 注意：股票可能会一直跌，因此将f[0][1]置为负无穷，并不能置为-1
    f[0][0] = 0, f[0][1] = -0x3f3f3f3f;
    for(int i = 1; i <= n; i ++){
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + w[i]);
        f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);
    }
    cout << max(f[n][0], f[n][1]) << endl;
    return 0;
}