Stock Profit With at Most K Trades

HardArraysDynamic programming263 tests

You get an array prices, where prices[d] is the price of one share on day d, and an integer k.

A trade is one buy followed later by one sell. The profit of a trade is the sell price minus the buy price.

Rules:

You may hold at most one share at any time. You must sell it before you buy again.
A sell must happen on a later day than its buy.
You may make at most k trades. Making fewer trades, or none, is allowed.

Return the largest total profit you can make. If no trade gives a profit, return 0.

Hint

Keep two numbers for every t from 1 to k: the best money you can have after the t-th buy, and the best money after the t-th sell. Update them day by day. The t-th buy starts from the money after the (t - 1)-th sell.

Examples

Example 1

Input:: [4,9,2,7,3,11], 2
Output:: 14

Buy at 4 and sell at 9 (profit 5). Then buy at 2 and sell at 11 (profit 9). The total is 14. A third trade would add more, but only 2 trades are allowed.

Example 2

Input:: [10,8,6,3], 3
Output:: 0

The price only falls, so every trade loses money. Make no trades.

Example 3

Input:: [1,5,2,6,3,7], 1
Output:: 6

With one trade, buy at 1 and sell at 7 for a profit of 6.

Constraints

0 <= prices.length <= 30
0 <= prices[d] <= 100
0 <= k <= 10

Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.