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

[fockspaces]

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note:

You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). The transaction fee is only charged once for each stock purchase and sale.

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8 Explanation: The maximum profit can be achieved by:

• Buying at prices[0] = 1
• Selling at prices[3] = 8
• Buying at prices[4] = 4
• Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3 Output: 6

Constraints:

1 <= prices.length <= 5 104 1 <= prices[i] < 5 104 0 <= fee < 5 * 104

[fockspaces]

這題沒寫過真的不會想到，我當時已經挺盡力寫出來（但仍須改進） buy：若買入當前股票，當前 profit sell：若賣出當前股票，當前 profit 注意初始值，buy 不可以是 0，因為不可能一開始就免費獲得一張股票，因此用 -inf 跳過判斷

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        buy, sell = float('-inf'), 0
        for i, price in enumerate(prices):
            prev_buy, prev_sell = buy, sell
            sell = max(prev_sell, prev_buy + price - fee)
            buy = max(prev_buy, prev_sell - price)
        return sell

[fockspaces]

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

1. 參考解法：https://www.youtube.com/watch?v=CBvPujbmWhU&ab_channel=HuifengGuan
2. 我的 code：

   class Solution:
   def maxProfit(self, prices: List[int], fee: int) -> int:
       buy, sell = float('-inf'), 0
       for i, price in enumerate(prices):
           prev_buy, prev_sell = buy, sell
           sell = max(prev_sell, prev_buy + price - fee)
           buy = max(prev_buy, prev_sell - price)
       return sell

   我後來參考了此影片的解法，了解到我原來的寫法，只能求局部的最優解，無法找到全局最優 原因為：原本一發現有更好的獲利組合，便將其考慮進去，而忽略了「後面仍可不在該天賣出股票」的選擇

新的解法使用了 buy, sell 兩個變數

• buy 用於記錄「當前持有股票時的最大獲益」：buy = max(prev_buy, prev_sell - price) 由於買入股票必須建立在「未持有股票」的情況，我們可以比較「目前已持有股票，故放棄買入這張股票」及「目前未持有股票，買入這張股票」的獲益情況
• sell 用於記錄「當前未持有股票時的最大獲益」：sell = max(prev_sell, prev_buy + price - fee) 賣出的行為只有在「已持有股票」時會發生，因此我們比較「當前未持有股票，因此不做賣出」及「當前持有股票，且將該股票賣出」的獲益情況

在最一開始，buy 必須設 -inf，因為我們還未買進股票，不能進行「賣出」的動作 接著我們不斷維護 buy, sell 兩個變數，最後 sell 即代表「將所有股票獲利了結」時的收益。