Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 309. Best Time to Buy and Sell Stock with Cooldown

---

題目：


方法：

1. hold：手上有股票
2. sold：今天剛賣掉
3. rest：今天沒操作（cooldown or rest）

hold[i] = max(hold[i − 1], rest[i − 1] − price[i])
  要嘛繼續持有
  要嘛今天買(只能從rest來)

sold[i] = hold[i − 1] + price[i]
  一定是昨天持有，加上今天賣

rest[i] = max(rest[i − 1], sold[i − 1])
  要嘛繼續休息
  要嘛剛賣完進入cooldown

解答：

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

        if (n == 0) {
            return 0;
        }

        int hold = -prices[0];
        int rest = 0;
        int sold = 0;

        for (int i = 1; i < n; ++i) {
            int pre_hold = hold;
            int pre_rest = rest;
            int pre_sold = sold;

            hold = max(pre_hold, pre_rest - prices[i]);
            sold = pre_hold + prices[i];
            rest = max(pre_sold, pre_rest);
        }

        return max(sold, rest);
    }
};