package leetcode;

/**
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
 */
public class Problem188 {
    public int maxProfit(int k, int[] prices) {
        // TODO
        return 0;
    }

    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,15 +175,866 @@
     
-// TODO
+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 maxProfit(int k, int%5B%5D prices, int index, boolean buy,%0A                                 Integer%5B%5D%5B%5D%5B%5D memo) %7B%0A        if (k == 0 %7C%7C prices.length == index) %7B%0A            return 0;%0A        %7D%0A        if (memo%5Bk%5D%5Bindex%5D%5Bbuy ? 0 : 1%5D != null) %7B%0A            return memo%5Bk%5D%5Bindex%5D%5Bbuy ? 0 : 1%5D;%0A        %7D%0A        int max = 0;%0A        int a = 0;%0A        if (buy) %7B%0A            a = maxProfit(k, prices, index + 1, !buy, memo) - prices%5Bindex%5D; // buy%0A        %7D else %7B%0A            a = maxProfit(k - 1, prices, index + 1, !buy, memo) + prices%5Bindex%5D; // sell%0A        %7D%0A        int b = maxProfit(k, prices, index + 1, buy, memo); // skip%0A        max = Math.max(max, Math.max(a, b));%0A        memo%5Bk%5D%5Bindex%5D%5Bbuy ? 0 : 1%5D = max;
 %0A   
@@ -1041,25 +1041,27 @@
      return 
-0
+max
 ;%0A    %7D%0A%0A   
@@ -1299,16 +1299,15 @@
 ); // 7%0A
- 
    %7D%0A%7D%0A

Update proble 188