Maximum Stock Profit: At Most K Transactions
Given a list prices, where prices[i] is the stock price on day i, return the maximum profit obtainable using at most k transactions.
A transaction consists of buying one stock and selling it on a later day. You must sell the currently held stock before buying again. If no profitable transaction is possible, return 0.
Method Signature
int maxProfit(int k, List<Integer> prices)
k is the maximum number of transactions allowed.prices contains the stock price for each day.- Return the maximum total profit.
Constraints
1 ≤ k ≤ 1001 ≤ prices.size() ≤ 1,0000 ≤ prices[i] ≤ 1,000
Examples
Example 1
Input: maxProfit(k = 2, prices = [1, 5, 2, 8])
Output: 10
Explanation: Buy at 1 and sell at 5 for a profit of 4. Then buy at 2 and sell at 8 for a profit of 6. The total profit is 10.
Example 2
Input: maxProfit(k = 1, prices = [7, 3, 6, 2, 5])
Output: 3
Explanation: Only one transaction is allowed. Buying at 3 and selling at 6 produces the maximum profit of 3.
Example 3
Input: maxProfit(k = 3, prices = [9, 7, 4, 1])
Output: 0
Explanation: The price continually decreases, so no profitable transaction is possible.