Best Time to Buy and Sell Stock with Transaction Fee

Medium20–25 min

Topics

Dynamic Programming

Companies

AmazonUberBloomberg

Given daily stock `prices`, buy and sell as many times as you like — no two positions open at once, so a share must be sold before another is bought — but every completed round trip costs a flat `fee`, charged when the position closes. Maximize total profit. Every day only asks one question: given whether a share is currently held, is acting (buying into nothing, or selling out of a position) better than leaving things exactly as they are? Two running totals capture everything needed to answer that — the best result with nothing held, and the best result already holding one share — and each day's decision only ever needs yesterday's version of those two numbers. The fee just gets folded into the moment of selling, so a trade only ever gets taken when the price gap actually covers it.

Test Case 1:

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

Output:8

Explanation:Buy at 1, sell at 8 for a net of 8-1-2=5, then buy at 4, sell at 9 for a net of 9-4-2=3. Total 5+3=8 — every other split of the same two runs pays the fee more often for less gain.

Test Case 2:

Input:prices = [1,2], fee = 5

Output:0

Explanation:The only possible trade nets 2-1=1 before the fee, but the fee itself is 5 — trading would lose money, so the best choice is never buying at all.

Test Case 3:

Input:prices = [7,6,4,3,1], fee = 1

Output:0

Explanation:Prices only ever fall, so no buy is ever followed by a higher sell price — the fee makes an already-bad trade worse, and doing nothing stays optimal throughout.

Constraints

◆1 ≤ prices.length ≤ 10
◆0 ≤ prices[i] ≤ 1000
◆0 ≤ fee ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursion Without Memoization

Brute

At every day there are only ever two live options: stay exactly as you are, or act on today's price — buy if nothing is held, sell (and pay the fee right there) if something is. Recursing through both choices at every day and keeping the better result is correct, but "staying as you are" and "acting" both lead back into the same solve(day, holding) shape from countless different histories, so the same day-and-position combination gets fully re-solved over and over as the array grows.

TimeO(2ⁿ)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] prices;
    private int fee;
    public int maxProfit(int[] prices, int fee) {
        this.prices = prices;
        this.fee = fee;
        return solve(0, false);
    }
    private int solve(int day, boolean holding) {
        if (day == prices.length) return 0;
        int doNothing = solve(day + 1, holding);
        int act;
        if (holding) {
            act = prices[day] - fee + solve(day + 1, false);
        } else {
            act = -prices[day] + solve(day + 1, true);
        }
        return Math.max(doNothing, act);
    }
}

Optimal — Bottom-Up 2-State DP

Optimal

Only two numbers ever matter as the days go by: the best total with nothing currently held (`cash`), and the best total assuming a share is currently held (`hold`, already down the price it cost to buy). Each new day can only improve one state from the other's *previous* value — cash improves if selling today (collecting the price and paying the fee) beats holding on, and hold improves if buying today beats whatever position was already held. Carrying just these two running numbers forward, one day at a time, replaces the exponential branching with a single linear pass.

TimeO(n)

SpaceO(1)