714. Best Time to Buy and Sell Stock with Transaction Fee

這題我覺得還是很難想像, 我用紙筆推了好多次, 我在這邊還是試圖筆記下來看能不能讓想法更清楚

一樣是可以無限次找買賣的點, 一天可以做買出跟賣出, 跟stock的第二題有點像

我們用兩個陣列來表示, sold表示第i天可能賣掉的價值, hold表示第i天手中保留的價值, 注意到這邊只有價值, 並不表示實際到底第i天是否買或賣或保留

舉個例子

[3,1,10,5]

第一天是

hold = -3
sold = 0

表示我現在買了這張股票, 目前還沒賣掉所以總共是-3的獲利

到了第二天

hold = -1
sold = 0

在這邊可以我當然比較輕向在第二天再拿就好, 畢竟第二天比較便宜

第三天

hold = -1
sold = 7

如果我還是握在手上, 那相當於我跟前一天一樣不變

但如果我賣掉我就能獲得10塊, 扣除手續費現賺7塊, 所以這邊sold最好是7

第四天

hold = 2
sold = 7

原本的hold是-1, 可是我可以發現假設我前一天用賣掉的價錢, 再加上今天買的價錢, 可以比原本我都不操作還要來得好, 那我當然傾向於前一天賣掉今天在買回來, 都是hold我這樣賺更多, 反之sold就不會有變動了, 因為如果昨天沒賣今天才賣, 那昨天賣還比較好勒

這邏輯我覺得還是有點繞, 需要多花幾次一直想, 不過有個方法就是扯到錢, 好像就會瞬間好理解XD

hold = max(hold[i -1], sold[i-1] -prices[i])

sold = max(sold[i-1], hold[i-1] + prices[i]-fee

class Solution {
public:
  int maxProfit(vector<int> &prices, int fee) {
    vector<int> sold(prices.size(), 0);
    vector<int> hold(prices.size(), 0);
    hold[0] = -prices[0];
    for(int i = 1; i < prices.size();i++){
        sold[i] = max(sold[i -1], hold[i - 1] + prices[i] - fee);
        hold[i] = max(hold[i - 1], sold[i -1] - prices[i]);
    }
      return sold[prices.size() -1];
  }
};