Dynamic Programming • State Machine

Best Time to Buy and Sell Stock with Transaction Fee

Maximize profit with unlimited transactions, but every time you sell the stock, you must pay a fixed transaction fee.

Overview

Without a fee, the optimal strategy is to capture every single price increase. With a fee, small fluctuations might cost more in fees than they yield in profit.

The State Machine

We only need two states: `Buy` (Holding a stock) and `Sell` (Cash in hand / Empty). There are no cooldowns.

The Fee Placement

You can subtract the fee when you buy (`prevSell - prices[i] - fee`) OR when you sell (`prevBuy + prices[i] - fee`). Mathematically, both give the exact same max profit.

Space Optimization

Since today's states only depend on yesterday's states, we don't need arrays. Two variables (`buy` and `sell`) are enough, yielding O(1) space.

Day 0: Price $1 (Fee: $2)

Buy (Hold)

-1

⇄

Sell (Cash)

0

Code Tracker

:::

1let buy = -prices[0];

2let sell = 0;

3for (let i = 1; i < prices.length; i++) {

4 let prevBuy = buy;

5 let prevSell = sell;

6 // We can buy at any time, just subtract price from cash

7 buy = Math.max(prevBuy, prevSell - prices[i]);

8 // When we sell, we must pay the transaction fee

9 sell = Math.max(prevSell, prevBuy + prices[i] - fee);

10}

11return sell;

Stock With Transaction Fee

Stock With Transaction Fee

Best Time to Buy and Sell Stock with Transaction Fee

Overview

The State Machine

The Fee Placement

Space Optimization

Best Time to Buy and Sell Stock with Transaction Fee

Overview

The State Machine

The Fee Placement

Space Optimization