Best Time to Buy and Sell Stock IV

Share

Given prices[] and integer k (max transactions), find maximum profit. One transaction = one buy + one sell.

Example 1
Input: k=2, prices=[2,4,1] → Output: 2
Example 2
Input: k=2, prices=[3,2,6,5,0,3] → Output: 7

Solution Approach

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).
Java
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)