Best Time to Buy and Sell Stock V
Real-world version: Freight Slot Trading DeskThe statement here is our own: the same inputs, outputs and technique.
prices[i] is the quoted price of one freight slot on day i. You run a desk that may complete at most k trades over those days.
A trade uses two different days i < j and comes in one of two shapes:
- a long: take the slot on day
iand hand it back on dayj, for a gain ofprices[j] - prices[i]; - a short: promise the slot on day
iand cover the promise on dayj, for a gain ofprices[i] - prices[j].
Only one trade may be open at a time, so a trade has to be closed before the next one opens. A new trade may open on the very same day the previous one closes. You may complete fewer than k trades, and completing none is allowed, in which case the total is 0.
Return the largest total gain you can finish with.
Examples
Example 1
- Input
- prices = [5,1,9,2], k = 2
- Output
- 15
One allowed pair of trades: a long taken on day 1 at 1 and handed back on day 2 at 9 gains 8, then a short promised on day 2 at 9 and covered on day 3 at 2 gains 7. The second trade opens on the day the first one closes, which the rules permit, and the total is 15.
Example 2
- Input
- prices = [9,4], k = 1
- Output
- 5
The one trade allowed is a short promised on day 0 at 9 and covered on day 1 at 4, which gains 9 - 4 = 5.
Example 3
- Input
- prices = [6,6,6,6,6,6], k = 3
- Output
- 0
Every quote is the same, so any trade in either direction gains 0. Completing no trades at all is allowed, so the total is 0.
Constraints
- 2 <= prices.length <= 10^3
- 1 <= prices[i] <= 10^9
- 1 <= k <= 500
- 2 * k <= prices.length
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def maximum_profit(prices: list[int], k: int) -> int:public long maximumProfit(int[] prices, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 17 test cases: 17 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's