LeetCode: 123. Best Time to Buy and Sell Stock III

题目大意

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目大意: 给定一个表示每天的股价的数组，求出最多两次买卖机会下，最大收益。

解题思路 —— 动态规划

• 每天的状态可能有五种情况: 一次都没有买卖, 第一次买入股票, 第一次卖出股票, 第二次买入股票, 第二次卖出股票。 由于一次都没有买卖的情况下，收益始终为 0，因此实际上我们只需要记录后四种状态。
• 记: lastProfixes[0...3] 分别为上一天第一次买入股票, 第一次卖出股票, 第二次买入股票, 第二次卖出股票四种状态下的最大收益
• 记: curProfixes[0...3] 分别为当天第一次买入股票, 第一次卖出股票, 第二次买入股票, 第二次卖出股票四种状态下的最大收益
• 前 i 天作为第一次买入股票的状态的最优解：”第 i 天前就已经第一次买入股票的最优解” 和 “第 i 天第一次买入股票(收益为 -prices[i](买入股票，收益为负))”的最大值。 即 curProfixes[0] = max(lastProfixes[0], 0-prices[i]);
• 前 i 天作为第一次卖出股票的状态的最优解: “第 i 天前就已经第一次卖出股票的最优解” 和 “第 i 天第一次卖出股票的收益(收益为第 i 天前第一次买入收益的最大值加上第 i 天卖出股票的收益(prices[i]+lastProfixes[0]))”的最大值, 即 curProfixes[1] = max(lastProfixes[1], prices[i]+lastProfixes[0]);
• 前 i 天作为第二次买入股票的状态的最优解: “第 i 天前就已经第二次买入股票的最优解” 和 “第 i 天第二次买入股票的收益(收益为第 i 天前第一次买入并卖出收益的最大值加上当日买入股票的收益(lastProfixes[1]-prices[i]))” 的最大值, 即 curProfixes[2] = max(lastProfixes[2], lastProfixes[1]-prices[i]);
• 前 i 天作为第二次卖出股票的状态的最优解: “第 i 天前就已经第二次卖出股票的最优解” 和 “第 i 天第二次卖出股票的收益(收益为第 i 天前第二次买入的收益的最大值加上当日卖出股票的收益(lastProfixes[2]+prices[i]))” 的最大值, 即 curProfixes[3] = max(lastProfixes[3], lastProfixes[2]+prices[i]);

AC 代码

class Solution {
private:
    // 枚举当前存在的状态
    const static int SELL_BUY_0_1 = 0;  // 第一次买入股票
    const static int SELL_BUY_1_1 = 1;  // 第一次卖出股票
    const static int SELL_BUY_1_2 = 2;  // 第二次买入股票
    const static int SELL_BUY_2_2 = 3;  // 第二次卖出股票
public:
    int maxProfit(vector<int>& prices) {
        // 保存上一天各种状态下的最大收益
        vector<int> lastProfixes {INT_MIN, 0, INT_MIN, 0};
        // 保存当天各种状态的最大收益
        vector<int> curProfixes{INT_MIN, 0, INT_MIN, 0};

        for(size_t i = 0; i < prices.size(); ++i)
        {
            // 第 i 天作为第一次买入股票的状态, 是否是第一次买入收益的最优解
            // 第 i 天第一次买入股票，则收益为 -prices[i]（买入股票，收益为负）
            curProfixes[SELL_BUY_0_1] = max(lastProfixes[SELL_BUY_0_1], 0-prices[i]);

            // 第 i 天作为第一次卖出股票的状态, 是否是第一次卖出收益的最优解
            // 第 i 天第一次卖出股票的收益为第 i 天前第一次买入收益的最大值加上第 i 天卖出股票的收益
            // 即 (prices[i]+lastProfixes[SELL_BUY_0_1])
            curProfixes[SELL_BUY_1_1] = max(lastProfixes[SELL_BUY_1_1], 
                    prices[i]+lastProfixes[SELL_BUY_0_1]);

            // 第 i 天作为第二次买入股票的状态, 是否是第二次买入收益的最优解
            // 第 i 天第二次买入股票的收益为第 i 天前第一次买入并卖出收益的最大值加上当日买入股票的收益
            // 即 (lastProfixes[SELL_BUY_1_1]-prices[i])
            curProfixes[SELL_BUY_1_2] = max(lastProfixes[SELL_BUY_1_2],
                    lastProfixes[SELL_BUY_1_1]-prices[i]);

            // 第 i 天作为第二次卖出股票的状态, 是否是第二次卖出收益的最优解
            // 第 i 天第二次卖出股票的收益为第 i 天前第二次买入的收益的最大值加上当日卖出股票的收益
            // 即 (lastProfixes[SELL_BUY_1_2]+prices[i])
            curProfixes[SELL_BUY_2_2] = max(lastProfixes[SELL_BUY_2_2], 
                    lastProfixes[SELL_BUY_1_2]+prices[i]);

            // 一天过去了...
            lastProfixes = curProfixes;
        }

        // 买卖一次？ 买卖两次？ 收益最大
        return max(curProfixes[SELL_BUY_1_1], curProfixes[SELL_BUY_2_2]);
    }
};