#714

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock with Transaction Fee

Maximize stock trading profits accounting for per-transaction fees using state transition dynamic programming and greedy optimization strategies.

array dynamic programming greedy

Problem Statement

You are given an array prices where prices[i] represents the price of a given stock on the ith day, along with an integer fee representing a transaction fee. You may complete as many transactions as you like but must pay the fee for each sale. Determine the maximum profit you can earn by choosing optimal buy and sell days while accounting for the fee.

Each transaction consists of buying and then selling one share of the stock. You cannot engage in multiple simultaneous transactions, meaning you must sell before buying again. The challenge is to decide the exact days to buy and sell to maximize total profit while minimizing the impact of transaction fees, applying a state transition dynamic programming pattern.

Examples

Example 1

Input: prices = [1,3,2,8,4,9], fee = 2

Output: 8

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

Example details omitted.

Constraints

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

Solution Approach

Define State Variables

Use two variables: hold for the maximum profit while holding a stock, and cash for the maximum profit when not holding a stock. Initialize hold as -prices[0] and cash as 0. This setup tracks optimal decisions at each step while reflecting the core state transition dynamic programming pattern.

Iterate Through Prices

For each day, update cash as the maximum of previous cash and hold plus current price minus fee, representing selling today. Update hold as the maximum of previous hold and cash minus current price, representing buying today. This iteration captures the greedy aspect of taking optimal local actions to reach global maximum profit.

Return Maximum Profit

After processing all days, the maximum achievable profit is the value of cash. This ensures the solution ends in a legal state without holding a stock, consistent with the state transition rules for this problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each price is processed once, updating constant state variables. Space complexity is O(1) since only two variables are maintained regardless of input size.

What Interviewers Usually Probe

Look for a clear state representation separating holding vs not holding stock.
Expect efficient O(n) solution rather than nested loops for multiple transactions.
Check for correct handling of the transaction fee on each sell operation.

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract the transaction fee when updating cash after a sell.
Using extra arrays for all states, increasing space complexity unnecessarily.
Mixing the order of updates for hold and cash, leading to incorrect state transitions.

Follow-up variants

Restrict number of transactions to K and adapt the state transition DP accordingly.
Introduce cooldown periods after selling, requiring additional state tracking.
Allow multiple stocks with independent fees, extending the DP state dimensions.

FAQ

What is the key pattern to solve Best Time to Buy and Sell Stock with Transaction Fee?

The main pattern is state transition dynamic programming, tracking maximum profit while holding or not holding stock.

How do I account for transaction fees in this problem?

Subtract the fee from the profit whenever you sell a stock, updating your cash state accordingly.

Can I use greedy without dynamic programming?

Pure greedy fails for complex sequences; the correct approach combines greedy updates with state transitions to account for fees.

What is the time and space complexity of this solution?

Time complexity is O(n) for iterating prices once, and space complexity is O(1) using only two variables.

Why can't I hold multiple stocks simultaneously in this problem?

The problem constraints allow only one stock per transaction cycle, ensuring state transitions remain valid.

terminal

Solution

Solution 1: Memoization

We design a function $dfs(i, j)$, which represents the maximum profit that can be obtained starting from day $i$ with state $j$. Here, $j$ can take the values $0$ and $1$, representing not holding and holding a stock, respectively. The answer is $dfs(0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

Solution 2: Dynamic Programming

We define $f[i][j]$ as the maximum profit that can be obtained up to day $i$ with state $j$. Here, $j$ can take the values $0$ and $1$, representing not holding and holding a stock, respectively. We initialize $f[0][0] = 0$ and $f[0][1] = -prices[0]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(prices):
                return 0
            ans = dfs(i + 1, j)
            if j:
                ans = max(ans, prices[i] + dfs(i + 1, 0) - fee)
            else:
                ans = max(ans, -prices[i] + dfs(i + 1, 1))
            return ans

        return dfs(0, 0)

Continue Practicing

#646 maximum length of pair chain #871 minimum number of refueling stops #435 non overlapping intervals