Best Time to Buy and Sell Stock V
You are given an integer array prices where prices[i] is the price of a stock in dollars on the i^th day, and an integer k.
You are allowed to make at most k transactions, where each transaction can be either of the following:
- Normal transaction: Buy on day
i, then sell on a later dayjwherei < j. You profitprices[j] - prices[i]. - Short selling transaction: Sell on day
i, then buy back on a later dayjwherei < j. You profitprices[i] - prices[j].
Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.
Return the maximum total profit you can earn by making at most k transactions.
Example 1
Input
prices = [1,7,9,8,2], k = 2Output
14A normal transaction from day 0 to day 2 earns 8, and a short selling transaction from day 3 to day 4 earns 6, for a total profit of 14.
Example 2
Input
prices = [12,16,19,19,8,1,19,13,9], k = 3Output
36The three transactions earn profits 7, 11, and 18 respectively, for a total profit of 36.
Constraints
- 2 <= prices.length <= 10^3
- 1 <= prices[i] <= 10^9
- 1 <= k <= prices.length / 2