FunctionRacerProblemsRace

At Most K Trades

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

prices[i] is the price of one share on day i. A trade buys one share on some day and sells it on a later day. You hold at most one share at a time, so a trade must end before the next one begins (selling and buying again on the same day is allowed).

Return the largest total profit from at most k trades. Making no trade gives 0.

Example 1

prices [5,9,2,3,8]
k 2
returns 10

Buy at 5 and sell at 9, then buy at 2 and sell at 8: 4 + 6 = 10.

Example 2

prices [5,9,2,3,8]
k 1
returns 6

With one trade only, buy at 2 and sell at 8.

Example 3

prices [9,7,4]
k 3
returns 0

The price only falls, so it is best not to trade.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems