Best Time to Buy and Sell Stock with Transaction Fee
MediumDynamic programmingLeetCode 714 ↗World 5-6Trade as often as you like, but every sale costs a fee. Track two states, cash and holding, and update both each day in one pass.
▼The problem
LeetCode 714 (Medium). prices[i] is the price of a stock on day i and fee is charged once per completed transaction (a buy and its sell). Trade as many times as you like, holding at most one share at a time. Return the maximum profit. (Cousins in the series: ../best-time-to-buy-stock (one trade, the market monitor) and ../best-time-to-buy-and-sell-stock-with-cooldown (three states, the cottage); this one has its own look.)
Examples (LeetCode's): prices = [1,3,2,8,4,9], fee = 2 → 8 (buy 1 sell 8: 7 − 2 = 5; buy 4 sell 9: 5 − 2 = 3; walked through in scene 7) and prices = [1,3,7,5,10,3], fee = 3 → 6 (one trip, 1 to 10: 9 − 3 = 6).
The solution
def maxProfit(prices, fee):
cash, hold = 0, -prices[0]
for p in prices[1:]:
cash = max(cash, hold + p - fee)
hold = max(hold, cash - p)
return cashTranscript
Best Time to Buy and Sell Stock with Transaction Fee. Each day has a price. Trade as often as you like, holding one share at most, but every finished trade pays a fee. Find the most profit.
Prices one, three, two, eight, four, nine, and a fee of two. Buy at one, sell at eight: seven, minus the fee, five. Buy at four, sell at nine: three more. Eight. Prices one, three, seven, five, ten, three, fee three, give six.
The naive way tries every choice: each day, trade or wait: two to the n paths.
The fee changes things. With no fee, you'd ride every rise: one to three, then two to eight. A fee of two eats the first trip whole, so one long trip, one to eight, wins.
So keep two ledgers. Cash: the best profit holding nothing. Hold: the best profit owning a share. Each day, cash may sell: hold plus the price, minus the fee. Hold may buy: cash minus the price. Keep the larger.
In code, cash starts at zero, and hold at minus the first price. For each price, update cash, then hold. Return cash.
Let's walk it. Price three: selling nets zero, so cash stays zero. Price two: nothing changes. Price eight: sell, cash is five. Price four: buy back, hold is one. Price nine: sell again, cash is eight.
One pass, two numbers: order n time and order one space.
Two ledgers, one pass, one fee per trade. That's Best Time to Buy and Sell Stock with Transaction Fee.