package leetcode;

/**
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
 */
public class Problem188 {
    public int maxProfit(int k, int[] prices) {
        Integer[][][] memo = new Integer[k + 1][prices.length + 1][2];
        return maxProfit(k, prices, 0, true, memo);
    }

    private static int maxProfit(int k, int[] prices, int index, boolean buy,
                                 Integer[][][] memo) {
        if (k == 0 || prices.length == index) {
            return 0;
        }
        if (memo[k][index][buy ? 0 : 1] != null) {
            return memo[k][index][buy ? 0 : 1];
        }
        int max = 0;
        int a = 0;
        if (buy) {
            a = maxProfit(k, prices, index + 1, !buy, memo) - prices[index]; // buy
        } else {
            a = maxProfit(k - 1, prices, index + 1, !buy, memo) + prices[index]; // sell
        }
        int b = maxProfit(k, prices, index + 1, buy, memo); // skip
        max = Math.max(max, Math.max(a, b));
        memo[k][index][buy ? 0 : 1] = max;
        return max;
    }

    public static void main(String[] args) {
        Problem188 prob = new Problem188();
        System.out.println(prob.maxProfit(2, new int[]{2, 4, 1})); // 2
        System.out.println(prob.maxProfit(2, new int[]{3, 2, 6, 5, 0, 3})); // 7
   }
}

@@ -175,121 +175,584 @@
     
-Integer%5B%5D%5B%5D%5B%5D memo = new Integer%5Bk + 1%5D%5Bprices.length + 1%5D%5B2%5D;%0A        return maxProfit(k, prices, 0, true, memo)
+// the k can be ridiculously high.%0A        if (k %3E= prices.length / 2) %7B%0A            return quickSolve(prices);%0A        %7D%0A        Integer%5B%5D%5B%5D%5B%5D memo = new Integer%5Bk + 1%5D%5Bprices.length + 1%5D%5B2%5D;%0A        return maxProfit(k, prices, 0, true, memo);%0A    %7D%0A%0A    private static int quickSolve(int%5B%5D prices) %7B%0A        int len = prices.length;%0A        int profit = 0;%0A        for (int i = 1; i %3C len; i++) %7B%0A            // as long as there is a price gap, we gain a profit.%0A            if (prices%5Bi%5D %3E prices%5Bi - 1%5D) profit += prices%5Bi%5D - prices%5Bi - 1%5D;%0A        %7D%0A        return profit
 ;%0A  
@@ -1522,255 +1522,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem188 prob = new Problem188();%0A        System.out.println(prob.maxProfit(2, new int%5B%5D%7B2, 4, 1%7D)); // 2%0A        System.out.println(prob.maxProfit(2, new int%5B%5D%7B3, 2, 6, 5, 0, 3%7D)); // 7%0A   %7D
 %0A%7D%0A

Solve problem 188