Sneaker Resale With a Shipping Day
You resell one popular sneaker model from a small flat. There is room for only one pair at a time. A price tracker gives you a good forecast of the price for each of the next few days, and you can buy or sell at that day's price.
Every sale has to be packed and taken to the post office the next day, which eats the whole day. So on the day right after a sale you cannot buy. You can repeat buy-and-sell rounds as often as you like. How much can you make?
Your task
Write maxProfit(prices). prices[d] is the price on day d. Each day you do one thing: buy a pair (only if you hold none), sell your pair (only if you hold one), or wait. After a sale on day d, you may not buy on day d + 1.
Return the largest total profit (money from sales minus money spent on buying). Ending with a pair still unsold only loses money, so the best plan never does it. If no trade makes money, return 0.
maxProfit(prices: int[]) → int
Examples
prices = [4, 7, 2, 9, 1, 6]
8
Buy at 4, sell at 7 (+3). Day 2 is the shipping day. Wait on day 3. Buy at 1, sell at 6 (+5). Total 8. The biggest single jump, 2 to 9, earns 7, but selling on day 3 makes day 4 a shipping day, so you miss the 1 and end with 7.
prices = [3, 5, 2, 6]
4
Without the shipping day you could earn 2 + 4 = 6. But selling at 5 on day 1 blocks buying at 2 on day 2. The best is one trade: buy at 2, sell at 6.
Constraints
- 0 ≤ prices.length ≤ 5,000
- 0 ≤ prices[d] ≤ 1,000
Start with brute force
Try every plan: each day buy, sell or wait, where the rules allow. That is up to 3ⁿ plans; for 30 days it is already about 2 × 10¹⁴, and the limit is 5,000 days.
The well-known trick for unlimited trades, adding up every rise from one day to the next, ignores the shipping day. It gives 6 on the second example, where only 4 is possible.
Hints
0 of 4 shown- Hint 1
At the end of any day, what situations can you be in? Try listing them for the second example. Is "I have no pair" enough information to decide what you may do tomorrow?
- Hint 2
No: an empty-handed day right after a sale is different from an ordinary empty-handed day, because tomorrow you may not buy. So there are three situations: holding a pair, just sold today, and free (no pair, allowed to buy tomorrow).
- Hint 3
Track the best profit so far for each of the three situations. How can you get into each one today? Holding: you held yesterday, or you were free yesterday and buy today. Just sold: you held yesterday and sell today. Free: you were free yesterday, or you sold yesterday (today is the shipping day).
- Hint 4
Walk the days once, updating three numbers from yesterday's three:
hold = max(hold, free - price),sold = holdBefore + price,free = max(free, soldBefore). Start withhold = -infinityand the others at 0. Compute all three from the old values before overwriting. The answer is the larger ofsoldandfree.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The rules depend on what happened yesterday, so the state must remember it. Three situations are enough: hold (you own a pair), sold (you sold today, so tomorrow you cannot buy), and free (no pair, and you may buy tomorrow). For each one, keep the best profit that ends the day in that situation.
Trace [3, 5, 2, 6]. Start: hold = -∞, sold = 0, free = 0.
- Day 0, price 3: hold = max(-∞, 0 - 3) = -3. sold = -∞ + 3 = -∞. free = max(0, 0) = 0.
- Day 1, price 5: hold = max(-3, 0 - 5) = -3. sold = -3 + 5 = 2. free = max(0, -∞) = 0.
- Day 2, price 2: hold = max(-3, 0 - 2) = -2. Buying here uses free = 0 from yesterday, not the 2 from yesterday's sale: that money is in
sold, which cannot buy today. sold = -3 + 2 = -1. free = max(0, 2) = 2. - Day 3, price 6: hold = max(-2, 2 - 6) = -2. sold = -2 + 6 = 4. free = max(2, -1) = 2.
Answer max(4, 2) = 4. The shipping-day rule lives in one place: sold only flows into free a day later, never straight into a buy.
function maxProfit(prices) {
let hold = -Infinity; // best profit while holding a pair
let sold = 0; // best profit if we sold today
let free = 0; // best profit with no pair and free to buy tomorrow
for (const p of prices) {
const prevHold = hold, prevSold = sold, prevFree = free;
hold = Math.max(prevHold, prevFree - p); // keep holding, or buy today
sold = prevHold + p; // sell the pair we held
free = Math.max(prevFree, prevSold); // wait, or today is the shipping day
}
return Math.max(sold, free);
}def max_profit(prices):
hold = float("-inf") # best profit while holding a pair
sold = 0 # best profit if we sold today
free = 0 # best profit with no pair and free to buy tomorrow
for p in prices:
hold, sold, free = (
max(hold, free - p), # keep holding, or buy today
hold + p, # sell the pair we held
max(free, sold), # wait, or today is the shipping day
)
return max(sold, free)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.