Given prices[] and integer k (max transactions), find maximum profit. One transaction = one buy + one sell.
Input: k=2, prices=[2,4,1] → Output: 2Input: k=2, prices=[3,2,6,5,0,3] → Output: 7
DP with states: dp[t][0]=max profit with t transactions, not holding; dp[t][1]=holding. If k >= n/2 (unlimited), use greedy.
- If k >= n/2: unlimited transactions, sum all positive diffs.
- Otherwise: dp arrays of size k+1 for hold and cash states.
- cash[t] = max(cash[t], hold[t] + price); hold[t] = max(hold[t], cash[t-1] - price).
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) {
int profit = 0;
for (int i = 1; i < n; i++) if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1];
return profit;
}
int[] cash = new int[k + 1], hold = new int[k + 1];
java.util.Arrays.fill(hold, Integer.MIN_VALUE);
for (int price : prices) {
for (int t = k; t >= 1; t--) {
cash[t] = Math.max(cash[t], hold[t] + price);
hold[t] = Math.max(hold[t], cash[t-1] - price);
}
}
return cash[k];
}
}
- Time Complexity: O(N * K)
- Space Complexity: O(K)