【leetcode】123. 买卖股票的最佳时机3

#include <vector>

using namespace std;

class Solution {
public:
    // 动态规划
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxProfit1(vector<int>& prices) {
        int n = prices.size();

        if (n == 0 || n == 1) return 0;
        
        // 每天交易完成后有5种状态：
        // -1. 不曾交易过
        // 0. 买过一次
        // 1. 买过一次，卖过一次
        // 2. 买过两次，卖过一次
        // 3. 买过两次，卖过两次
        // 因为状态-1不会对现金产生影响，因此不记录此状态
        // cur_cash表示每天交易完成后的最大现金
        // vector<vector<int>> cur_cash(n, vector<int>(4));
        // 由于每天只用到了上一天的状态，因此可以使用8个变量来代替二维数组
        int pre_buy_one{ -prices[0] },  // 第一天买了股票则现金为-prices[0]
            pre_sell_one{ 0 },  // 第一天没股票可卖
            pre_buy_two{ -prices[0] },  // 第一天最多买一次股票
            pre_sell_two{ 0 },  // 第一天没股票可卖
            cur_buy_one{ 0 },
            cur_sell_one{ 0 },
            cur_buy_two{ 0 },
            cur_sell_two{ 0 };

        for (int i = 1; i < n; i++) {
            // 状态转移方程
            // 前一天买过一次/当天买了一次 -> 当天买过一次
            cur_buy_one = max(pre_buy_one, -prices[i]);  
            // 前一天卖过一次/前一天买过一次当天卖了一次 
            // -> 当天买过一次卖过一次
            cur_sell_one = max(pre_sell_one, cur_buy_one + prices[i]);
            // 前一天买过两次卖过一次/前一天买过一次卖过一次，当天又买了一次
            // -> 当天买过两次卖过一次
            cur_buy_two = max(pre_buy_two, pre_sell_one - prices[i]);
            // 前一天买过两次卖过两次/前一天买过两次卖过一次，当天又卖了一次 
            // -> 当天买过两次卖过两次
            cur_sell_two = max(pre_sell_two, pre_buy_two + prices[i]);

            pre_buy_one = cur_buy_one;
            pre_sell_one = cur_sell_one;
            pre_buy_two = cur_buy_two;
            pre_sell_two = cur_sell_two;
        }

        return cur_sell_two;  // 充分利用次数
    }

    // 动态规划优化
    // 上面状态转移方程中的pre_*可以换成cur_*，因此可以只使用4个变量而非8个变量。
    // 例如在计算cur_sell_one时，使用cur_sell_one而非pre_sell_one来进行状态转移
    // cur_buy_one比pre_buy_one多考虑了当天买了的情况，而状态转移至cur_sell_one
    // 时，考虑的是当天卖出的情况，同一天内的买卖并不会对现金产生影响。
    // 时间复杂度O(n)，空间复杂度O(1)
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        if (n == 0 || n == 1) return 0;

        // 此时物理含义仍为每天交易完成后拥有的现金
        int buy_one{ -prices[0] },  // 第一天买了股票则现金为-prices[0]
            sell_one{ 0 },  // 第一天没股票可卖
            buy_two{ -prices[0] },  // 第一天最多买一次股票
            sell_two{ 0 };  // 第一天没股票可卖

        for (int i = 1; i < n; i++) {
            // 状态转移方程
            // 买过一次/买了一次 -> 买过一次
            buy_one = max(buy_one, -prices[i]);
            // 前一天卖过一次/前一天买过一次当天卖了一次 
            // -> 当天买过一次卖过一次
            sell_one = max(sell_one, buy_one + prices[i]);
            // 前买过两次卖过一次/买过一次卖过一次，又买了一次
            // -> 买过两次卖过一次
            buy_two = max(buy_two, sell_one - prices[i]);
            // 买过两次卖过两次/买过两次卖过一次，又卖了一次 
            // -> 买过两次卖过两次
            sell_two = max(sell_two, buy_two + prices[i]);
        }

        return sell_two;  // 充分利用次数
    }


    // 自己错误写法，想着挑最大的两段出来，结果发现此思想并不可取
    // 如[1,2,4,2,5,7,2,4,9,0]
    //          ↑   ↑ ↑   ↑
    //         买   卖买  卖
    // 按此思想会取7-2和9-2，但实际上最优解为7-1和9-2
    // [1,2,4,2,5,7,2,4,9,0]
    //  ↑         ↑ ↑   ↑
    //  买        卖买  卖
    // 感觉比较困难
    void update_top2_profit(int&max_profit, int& second_max_profit, int& cur_profit) {
        if (cur_profit >= max_profit) {
            second_max_profit = max_profit;
            max_profit = cur_profit;
        }
        else if (cur_profit >= second_max_profit) {
            second_max_profit = cur_profit;
        }
    }

    int maxProfit_error(vector<int>& prices) {
        int n = prices.size();

        if (n == 0 || n == 1) return 0;

        int max_profit{ 0 }, second_max_profit{ 0 },
            min_price{ prices[0] }, cur_profit{ 0 };

        for (int i = 1; i < n; i++) {
            if (i == n - 1 && prices[i] >= prices[i - 1]) {
                cur_profit = prices[i] - min_price;
                update_top2_profit(max_profit, second_max_profit, cur_profit);
            }
            else  if (prices[i] < prices[i - 1]) {
                cur_profit = prices[i - 1] - min_price;
                update_top2_profit(max_profit, second_max_profit, cur_profit);
                min_price = prices[i];
            }
        }

        return max_profit + second_max_profit;
    }
};


int main() {
    Solution s;
    vector<int> input{ 1,2,4,2,5,7,2,4,9,0 };

    int output;
    output = s.maxProfit(input);

    return output;
}