Exchange Rehearsal Profit Ladder
Maximum profit for each exact transaction count from a price array and fee
A stock exchange is testing a trading simulator against a tape of daily closing prices. The simulator trades a single share at a time and must report a profit ladder, rather than just its best unrestricted profit.
You are given an array prices, a nonnegative selling fee, and an integer k. On each day, the simulator may perform at most one action:
- Buy one share at that day's price, provided it is not already holding a share.
- Sell its held share at that day's price, paying
feefor that sale. - Do nothing.
A completed transaction consists of a purchase followed by a sale on a strictly later day. Shares cannot be sold before they are purchased. The simulator starts and finishes without a share. There is no restriction on available cash when buying.
Return an array of length k + 1. Its entry at index j must be the maximum net profit achievable with exactly j completed transactions. Net profit is the sum of sale prices minus purchase prices and selling fees.
The zero-transaction entry is zero. Entries for positive transaction counts may be negative: the simulator must complete the requested number of transactions even when every such plan loses money. The input guarantees that every requested transaction count is feasible.
Examples
Example 1
Input: prices = [2,7,1,8], fee = 1, k = 2 Output: [0,6,10]
For one transaction, buying on the first day and selling on the fourth day is optimal. For two transactions, the simulator can use the first two days for one transaction and the last two days for another, paying the fee on both sales.
Example 2
Input: prices = [9,7,5,3], fee = 2, k = 2 Output: [0,-4,-8]
Prices decrease throughout the tape. Exact transaction counts therefore force losses. For two transactions, all four days must be used, with purchases on days zero and two and sales on days one and three.
Example 3
Input: prices = [], fee = 0, k = 0 Output: [0]
With no days and no requested transactions, the ladder contains only its zero-transaction entry.
Constraints
- 0 <= prices.length <= 10000
- 0 <= prices[i] <= 1000000
- 0 <= fee <= 1000000
- 0 <= k <= 100
- 2 * k <= prices.length
An O(prices.length * k)-time, O(k)-extra-space solution is expected. Exactly j transactions is different from at most j transactions; do not replace negative ladder entries with zero.
Hints
Show hint 1Hint 1
Track the best result for each completed-transaction count separately, distinguishing whether a share is currently held.
Show hint 2Hint 2
A sale increases the completed count, while a purchase does not. Use only states from the previous day so that two actions cannot occur on the same day.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the states change if a sale forced the simulator to wait one full day before buying again?
- How could you reconstruct an optimal sequence of purchase and sale days for a specified entry of the ladder?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem