題目網址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

題意：給一整數 array prices, 其中第 i 個元素代表第 i 天的股價。

最多完成兩筆交易, 返回最大利潤。

注意：不能同時參與多筆交易（必須在再次購買前出售掉之前的股票）。

Solution 1：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 prices 前先加上一個 0, 代表什麼元素都沒有的狀態
  • hold1[i]：第 i 天買入第一支股票的最大收益
  • sold1[i]：第 i 天賣出第一支股票的最大收益
  • hold2[i]：第 i 天買入第二支股票的最大收益
  • hold2[i]：第 i 天賣出第二支股票的最大收益

2. 得到狀態轉移方程：

  • hold1[i]：可由以下兩種狀態轉移

    • 第 i - 1 天買入第一支, 第 i 天不操作 ➔ hold1[i - 1]
    • 第 i - 1 天不操作（沒任何股票）, 第 i 天買入第一支 ➔ 0 - prices[i]

    ➔ hold1[i] = max(hold1[i - 1], -prices[i])

  • sold1[i]：可由以下兩種狀態轉移

    • 第 i - 1 天賣出第一支, 第 i 天不操作 ➔ sold1[i - 1]
    • 第 i - 1 天不操作（買入第一支的狀態）, 第 i 天賣出第一支
      ➔ hold1[i - 1] + prices[i]

    ➔ sold1[i] = max(sold1[i - 1], hold1[i - 1] + prices[i])

  • hold2[i]：可由以下兩種狀態轉移

    • 第 i - 1 天買入第二支, 第 i 天不操作 ➔ hold2[i - 1]
    • 第 i - 1 天不操作（賣出第一支的狀態）, 第 i 天買入第二支
      ➔ sold1[i - 1] - prices[i]

    ➔ hold2[i] = max(hold2[i - 1], sold1[i - 1] - prices[i])

  • sold2[i]：可由以下兩種狀態轉移

    • 第 i - 1 天賣出第二支, 第 i 天不操作 ➔ sold2[i - 1]
    • 第 i - 1 天不操作（買入第二支的狀態）, 第 i 天賣出第二支
      ➔ hold2[i - 1] + prices[i]

    ➔ sold2[i] = max(sold2[i - 1], hold2[i - 1] + prices[i])

3. 初始化：

  • hold1[0]、sold1[0]、hold2[0]、sold2[0]：沒有股票時, 最大利潤為 0
  • hold1[1]：第一天買入股票 ➔ 此時的最大利潤為 prices[1]
  • sold1[1]：在第一天買入, 並且賣出 ➔ 此時的最大利潤為 0
  • hold2[1]：在第一天買入, 並且賣出, 然後再買入 ➔ 此時的最大利潤為 prices[1]
  • sold2[1]：在第一天買入, 並且賣出, 然後再買入、再賣出 ➔ 此時的最大利潤為 0
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int n = prices.size();
        vector<int> hold1(n + 1, 0), sold1(n + 1, 0);
        vector<int> hold2(n + 1, 0), sold2(n + 1, 0);

        prices.emplace(prices.begin(), 0);
        hold1[1] = -prices[1], hold2[1] = -prices[1];

        for (int i = 2; i <= n; ++i) {
            hold1[i] = max(hold1[i - 1], -prices[i]);
            sold1[i] = max(sold1[i - 1], hold1[i - 1] + prices[i]);
            hold2[i] = max(hold2[i - 1], sold1[i - 1] - prices[i]);
            sold2[i] = max(sold2[i - 1], hold2[i - 1] + prices[i]);
        }

        // 最大利潤必發生在沒有持有股票的狀態, 故不考慮 hold1, hold2
        return max(sold1.back(), sold2.back());
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ hold1, sold1, hold2, sold2

Solution 2：

想法：改進 Solution 1, 因為 hold1[i], sold1[i], hold2[i], sold2[i] 只會用到 i - 1 的狀態, 因此只要儲存 i - 1 的狀態即可, 根本不需要開到 $O(n)$ space

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        const int n = prices.size();

        prices.emplace(prices.begin(), 0);

        int hold1 = -prices[1], sold1 = 0, hold2 = -prices[1], sold2 = 0;

        for (int i = 2; i <= n; ++i) {
            const int prevHold1 = hold1, prevSold1 = sold1;
            const int prevHold2 = hold2, prevSold2 = sold2;

            hold1 = max(prevHold1, -prices[i]);
            sold1 = max(prevSold1, prevHold1 + prices[i]);
            hold2 = max(prevHold2, prevSold1 - prices[i]);
            sold2 = max(prevSold2, prevHold2 + prices[i]);
        }

        // 最大利潤必發生在沒有持有股票的狀態, 故不考慮 hold1, hold2
        return max(sold1, sold2);
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間