Best Time to Buy and Sell Stock with Transaction Fee
Problem
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, return the maximum profit you can achieve by completing as many transactions as you like, paying the fee for each transaction. You may not hold more than one share of the stock at a time.
- 1 ≤ prices.length ≤ 5 * 10⁴
- 1 ≤ prices[i] ≤ 5 * 10⁴
- 0 ≤ fee ≤ 5 * 10⁴
Example
prices = [1, 3, 2, 8, 4, 9], fee = 28The algorithm explores decisions day by day, tracking whether it currently holds stock. On day 0, it can buy at price 1 (holding = True). On day 3, it sells at price 8, paying fee 2, netting 8 - 2 - 1 = 5 profit. Then it buys again at day 4 price 4 and sells at day 5 price 9, netting 9 - 2 - 4 = 3 profit. Total profit is 5 + 3 = 8. The key is deciding at each day whether to buy, sell, or hold, considering the fee cost and future opportunities.
Approach
Straightforward Solution
A brute-force approach tries all buy/sell sequences, leading to exponential time complexity due to combinatorial explosion of transaction sequences.
Core Observation
At any day, the maximum profit depends on whether the stock is currently held or not. The decision to buy or sell affects future profits and must account for the transaction fee, which reduces the net gain from selling.
Path to Optimal
Recognizing the problem as a sequence of decisions with overlapping subproblems and optimal substructure suggests Dynamic Programming. The key insight is to model the problem as a state machine with two states per day: holding stock or not holding stock. The DP recurrence compares the profit of doing nothing versus buying or selling, incorporating the fee cost on selling. Memoization or caching avoids redundant computations, reducing complexity from exponential to linear.
Optimal Approach
Use a top-down DP with memoization on states (day, holding_stock). For each day, compute the max profit by either skipping the day or performing a buy/sell action depending on the holding state. Selling subtracts the fee from the profit. The answer is dp(0, 0), starting at day 0 with no stock held.
Time
O(n)
Each day and holding state pair is computed once and cached, resulting in 2*n states and O(1) work per state.
Space
O(n)
Memoization cache stores results for each day and holding state, totaling O(n) auxiliary space. The recursion stack depth is also O(n).
Pattern Spotlight
Dynamic Programming (State Machine)
Model the problem as a state machine with states representing holding or not holding stock; at each step, choose the action (buy, sell, or hold) that maximizes profit while accounting for transaction fees, and use memoization to avoid redundant calculations.
Solution
| 1 | from functools import cache
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def maxProfit(self, prices: List[int], fee: int) -> int:
|
| 5 | @cache
|
| 6 | def dp(day, holding_stock):
|
| 7 | if day >= len(prices):
|
| 8 | return 0
|
| 9 |
|
| 10 | max_profit = dp(day + 1, holding_stock)
|
| 11 |
|
| 12 | if holding_stock:
|
| 13 | max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))
|
| 14 | else:
|
| 15 | max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))
|
| 16 |
|
| 17 | return max_profit
|
| 18 |
|
| 19 | return dp(0, 0) |
Step-by-Step Solution
Recursively Explore Profit States with Memoization
| 5 | @cache
|
| 6 | def dp(day, holding_stock):
|
| 7 | if day >= len(prices):
|
| 8 | return 0
|
| 10 | max_profit = dp(day + 1, holding_stock)
|
| 12 | if holding_stock:
|
| 13 | max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))
|
| 14 | else:
|
| 15 | max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))
|
| 17 | return max_profit
|
Objective
To compute the maximum profit from a given day and holding state by recursively deciding to hold, buy, or sell.
Key Insight
The problem breaks down into two states per day: holding stock or not. For each state, the algorithm compares the profit of skipping the day versus performing the allowed action (buy if not holding, sell if holding). Memoization ensures each state is computed once, preventing exponential recomputation and enabling efficient linear-time solution.
Interview Quick-Check
Core Logic
The DP function models two states per day (holding or not) and chooses the maximum profit between skipping or performing a buy/sell action, incorporating the transaction fee on selling.
State & Boundaries
The base case returns 0 profit when the day index exceeds the last day, ensuring recursion termination.
Common Pitfalls & Bugs
Applying the fee on buying instead of selling or forgetting to memoize states can lead to incorrect results or exponential time.
Complexity
Memoization reduces the exponential recursion tree to O(n) states, each computed once.
Return Final Maximum Profit Starting Without Stock
| 19 | return dp(0, 0) |
Objective
To initiate the DP recursion from day 0 with no stock held and return the maximum achievable profit.
Key Insight
Starting from day 0 and not holding stock aligns with the problem's initial conditions. This call triggers the entire recursive exploration of all possible buy/sell sequences, leveraging memoization to efficiently compute the optimal profit.
Interview Quick-Check
Core Logic
The initial call dp(0, 0) represents starting at the first day without holding stock, which is the problem's initial state.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
max_profit = max(max_profit, prices[day] - fee + dp(day + 1, 0))Calculate max profit by either skipping or selling stock today, accounting for the fee.
Selling stock realizes profit equal to the current price minus the fee, transitioning to not holding state; comparing with skipping ensures the optimal choice is selected.
if day >= len(prices):Check if the current day exceeds the last day and return 0 profit if so.
This base case terminates recursion, ensuring that no further profit can be made beyond the last day.
max_profit = max(max_profit, -prices[day] + dp(day + 1, 1))Calculate max profit by either skipping or buying stock today.
Buying stock costs the current price (negative profit) and transitions to holding state; comparing with skipping ensures the best decision is chosen.
@cacheEnable memoization of dp results so repeated calls with the same (day, holding_stock) reuse cached profit instead of recomputing.
Decorating the DP function with @cache ensures each (day, holding_stock) state is computed only once, turning an exponential recursion tree into a linear-time DP over O(n) states.
def dp(day, holding_stock):Define the recursive DP function with parameters day and holding_stock.
This function encapsulates the problem's state space, allowing exploration of all possible decisions from any day and holding state, enabling memoization to avoid redundant computations.
if holding_stock:Check if currently holding stock to decide possible actions.
The holding state determines whether the algorithm can sell (if holding) or buy (if not holding), guiding the recursive decision tree.
return max_profitReturn the maximum profit computed for the current state.
Returning the computed max profit completes the recursion step, enabling memoization and propagation of optimal results up the call stack.
return dp(0, 0)Start the DP recursion from day 0 with no stock held.
This initial call represents the problem's starting condition and triggers the entire DP computation for maximum profit.
return 0Return 0 when recursion reaches beyond the last day.
Returning zero here correctly represents that no profit is possible after the last day, anchoring the DP recursion.
max_profit = dp(day + 1, holding_stock)Calculate profit by skipping the current day and maintaining the holding state.
This models the decision to do nothing on the current day, preserving the current holding state and deferring action to future days.
else:Enter the 'not holding stock' branch to evaluate the option of buying at the current price.
This line selects the branch for the state where no stock is currently held, so the algorithm can consider buying on this day instead of selling.
Test Your Understanding
Why does the transaction fee only apply when selling and not when buying?
Because a transaction is defined as a complete buy-sell pair, the fee is charged upon completing the transaction at selling, not at buying.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Best Time to Buy and Sell Stock with Transaction Fee from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Best Time to Buy and Sell Stock with Transaction Fee drill