题解 | #买卖股票的最好时机(三)#

思路解析： 首先分析状态，一共有5个状态，分别为不操作，第一次买入buy1，第一次卖出sale1，第二次买入buy2，第二次卖出sale2。 那么

//第一次买入时，赚取的最大利益为支出的费用，即-price[i]或者暂不执行第一次买入
buy1 = max(buy1,-price[i]); 
//第一次卖出时，赚取的最大利益为第一次买入时支出的费用与卖出时股票的价值和，或者暂不执行第一次卖出
sale1 = max(sale1,buy1 + price[i]);
//第二次买入时，赚取的最大利益为第一次卖出时获取的最大利益与此时的支出的费用或暂不执行第二次的买入
buy2 = max(buy2,sale1 - price[i]);
//第二次卖出时，赚取的最大利益为第二次买入时的最大利益与卖出时股票的价值和或暂不执行第二次卖出
sale2 = max(sale2,buy2 + price[i]);

基础版本

#include<iostream>
#include<algorithm>
using namespace std;
int price[100000],dp[200005][5] = {0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0;i < n;++i)
        cin >> price[i];
    dp[0][1] = -price[0];
    dp[0][3] = -price[0];
    for(int i = 1;i < n;++i){
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] - price[i]);
        dp[i][2] = max(dp[i - 1][2],dp[i - 1][1] + price[i]);
        dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] - price[i]);
        dp[i][4] = max(dp[i - 1][4],dp[i - 1][3] + price[i]);
    }
    cout << dp[n - 1][4];
    return 0;
}

空间复杂度进行优化后版本

#include<iostream>
#include<algorithm>
using namespace std;
int price[100000], dp[200005][5] = { 0 };
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,buy1 = 0,sale1 = 0,buy2 = 0,sale2 = 0;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> price[i];
    buy1 = -price[0];
    buy2 = -price[0];
    for (int i = 1; i < n; ++i) {
        buy1 = max(buy1, - price[i]);
        sale1 = max(sale1, buy1 + price[i]);
        buy2 = max(buy2, sale1 - price[i]);
        sale2 = max(sale2, buy2 + price[i]);
    }
    cout << sale2;
}