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

tags: Leetcode(C++)

題目 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/submissions/ 。

想法 :

​​​​原本以為跟第309題一樣的轉移方程，因為多了FEE的關係，導致可能會有買2次的轉移，所以刪掉rest。
​​​​buy(i) = max(buy(i-1), sell(i-1) - price[i]);
​​​​sell(i) = max(sell(i-1), buy(i-1) + price[i] - fee);

時間複雜度 : O(n)。

程式碼 :

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int l=prices.size(), sell_1=0, sell, buy_1=-1*prices[0], buy;
        
        if(l == 1) return 0;
        
        for(int i=1 ; i<l ; i++){
            buy=max(buy_1,sell_1-prices[i]);
            sell=max(sell_1,buy_1+prices[i]-fee);
            
            buy_1=buy;
            sell_1=sell;
        }
        
        return sell;
    }
};