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

[fockspaces]

this is a tricky problem, keyword : state transfer maintain the two variables

1. hold: if we must hold one stock, the maximun profit we can get
2. sold: if we leave no stock, the maximun profit we can get
3. first, hold we be -prices[0], means that we cannot take no cost for holding one stock
4. each time, we can either keep holding previous stock, or buy current stock with no stock state
5. each time, we can sold the current stock or keep leaving no stock state

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        hold, sold = -prices[0], 0
        for p in prices:
            hold, sold = \
                max(hold, sold - p), max(sold, hold + p - fee)
        return sold

[fockspaces]

this actually comes from 2D dp, we create two state "one_stock" and "no_stock" for update

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        with_no = [0 for _ in range(n)]
        with_one = [0 for _ in range(n)]
        with_no[0], with_one[0] = 0, -prices[0]
        for i in range(1, n):
            with_no[i] = max(with_no[i - 1], with_one[i - 1] + prices[i] - fee)
            with_one[i] = max(with_one[i - 1], with_no[i - 1] - prices[i])
        return with_no[-1]