Medium

Best Time to Buy and Sell Stock with Transaction Fee

LAB

Return the maximum profit from any number of transactions when each sale pays the given fee.

EXAMPLES

Example 1

Input
{
  "prices": [
    1,
    3,
    2,
    8,
    4,
    9
  ],
  "fee": 2
}

Output
8

FUNCTION SHAPE

prices: intArrayfee: int→int

SOLUTION NOTE

Same state machine as cooldown, but subtract fee when selling instead of skipping a day.

Reveal reference solution +

pythonREFERENCE

def maxProfit(self, prices: List[int], fee: int) -> int:
    @cache
    def dp(i, holding):
        if i >= len(prices): return 0
        if holding:
            return max(prices[i] - fee + dp(i+1, False), dp(i+1, True))
        else:
            return max(-prices[i] + dp(i+1, True), dp(i+1, False))

    return dp(0, False)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗