方法一:贪心

思路:

任何一个跨度大于1天的交易都可以等价为若干个跨度等于1天的交易，即任意一种买卖方式可拆分成跨度均为1天的买卖。(如1，2，3，4，5，第一天买入在第5天卖出，为最大盈利4，可以拆分成1买2卖+2买3卖+3买4卖+4买5卖，简而言之就是遇增则买)

原理:

1.c - a = (b - a) + (c - b)：任何一个跨度天数大于1的交易(a价天买，c价天卖)，等价于拆分成的若干个(c-a个)连续的单天跨度交易(即与他们中间这些天的价格b无关，即使跌价，b较a跌得越狠，c较b升得就越快，两者效果抵消)

2.一个区间天数(左端点时刻买入，右端点时刻卖出)内盈利最大时，对应的集合$\{(a_t,a_{t+1}),(a_{t+1},a_{t+2}),…\}$中每一个区间均为正值(存在负值就该剔除)，即每个单天跨度都是递增的，故要想在整个时间线上盈利最大，即只在所有递增的子区间进行交易

代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
int price[N];

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> price[i];
    int res = 0;
    for(int i = 0;i + 1 < n;i ++)
    {
        int dt = price[i+1] - price[i];
        if(dt > 0)
            res += dt;
    }
    cout << res << endl;
    return 0;
}

方法二:DP

思路:

代码:

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

int main() 
{
    int N;
    cin >> N; 
    vector<int> price(N);
    for (int i = 0; i < N; i++) 
        cin >> price[i];  // 读入每天的股票价格

    // dp[i][0] 表示第 i 天结束时不持有股票的最大利润
    // dp[i][1] 表示第 i 天结束时持有股票的最大利润
    vector<vector<int>> dp(N, vector<int>(2, 0));

    // 初始化第 0 天的状态
    dp[0][0] = 0;          // 第 0 天不持有股票 利润为 0
    dp[0][1] = -price[0];  // 第 0 天买入股票 利润为 -price[0]

    // 从第 1 天开始更新状态
    for (int i = 1; i < N; i ++) {
        // 如果第 i 天结束时不持有股票，有两种情况：
        // 1. 前一天不持有股票，不操作，利润为 dp[i-1][0]
        // 2. 前一天持有股票，今天卖出，利润为 dp[i-1][1] + price[i]
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]);

        // 如果第 i 天结束时持有股票，有两种情况：
        // 1. 前一天已经持有股票，不操作，利润为 dp[i-1][1]
        // 2. 前一天不持有股票，今天买入股票，利润为 dp[i-1][0] - price[i]
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]);
    }

    // 最终答案是最后一天不持有股票的状态(获利要兑现)
    cout << dp[N-1][0] << endl;

    return 0;
}