Best Time to Buy and Sell Stock with Transaction Fee

The key idea

Track two running states: cash, the best profit while holding no stock, and hold, the best profit while holding one share. Each day update both. The fee is paid once per completed trade, charged on the sell, so selling only helps when the gain clears the fee.

Problem

You are given an array prices where prices[i] is the price of a given stock on the i-th day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

You may not buy more than one share of the stock at a time (you must sell the stock before you buy again).

The transaction fee is only charged once for each buy-and-sell pair.

Constraints

1 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4
0 <= fee < 5 * 10^4

Examples

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

Input: prices = [1,3,7,5,10,3], fee = 3 Output: 6

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →