package com.fishercoder.solutions;

/**
 * 188. Best Time to Buy and Sell Stock IV
 *
 * Say you have an array for which the ith element is the price of a given stock on day i.

 Design an algorithm to find the maximum profit. You may complete at most k transactions.

 Note:
 You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 */
public class _188 {

    /**credit: https://discuss.leetcode.com/topic/8984/a-concise-dp-solution-in-java*/
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (k >= len / 2) {
            return quickSolve(prices);
        }

        int[][] t = new int[k + 1][len];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }


    private int quickSolve(int[] prices) {
        int len = prices.length;
        int profit = 0;
        for (int i = 1; i < len; i++) {
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }

}

@@ -33,18 +33,17 @@
 s;%0A%0A/**%0A
- *
+%0A
  188. Be
@@ -79,13 +79,9 @@
  IV%0A
- *%0A *
+%0A
  Say
@@ -382,40 +382,430 @@
 n).%0A
- */%0Apublic class _188 %7B%0A
+%0A Example 1:%0A Input: %5B2,4,1%5D, k = 2%0A Output: 2%0A Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.%0A%0A Example 2:%0A Input: %5B3,2,6,5,0,3%5D, k = 2%0A Output: 7%0A Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.%0A Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.%0A%0A */%0Apublic class _188 %7B%0A  public static class Solution1 %7B
 %0A    /**
 cred
@@ -800,16 +800,17 @@
 %0A    /**
+ 
 credit: 
@@ -878,16 +878,17 @@
 -in-java
+ 
 */%0A    p
@@ -928,34 +928,32 @@
 prices) %7B%0A      
- 
- 
 int len = prices
@@ -957,26 +957,24 @@
 ces.length;%0A
-  
       if (k 
@@ -991,28 +991,24 @@
 ) %7B%0A        
-    
 return quick
@@ -1028,18 +1028,16 @@
 ;%0A      
-  
 %7D%0A%0A     
@@ -1037,18 +1037,16 @@
 %0A%0A      
- 
- 
 int%5B%5D%5B%5D 
@@ -1068,34 +1068,32 @@
  1%5D%5Blen%5D;%0A      
-  
 for (int i = 1; 
@@ -1111,28 +1111,24 @@
 ) %7B%0A        
-   
- 
 int tmpMax =
@@ -1127,17 +1127,16 @@
 tmpMax =
- 
  -prices
@@ -1140,20 +1140,16 @@
 ces%5B0%5D;%0A
-    
         
@@ -1190,22 +1190,16 @@
         
- 
-     
 t%5Bi%5D%5Bj%5D 
@@ -1257,22 +1257,16 @@
     
-  
-    
 tmpMax =
   Ma
@@ -1261,17 +1261,16 @@
 tmpMax =
- 
  Math.ma
@@ -1313,36 +1313,32 @@
 %5D);%0A        
-    
 %7D%0A      
   %7D%0A        
@@ -1317,38 +1317,34 @@
         %7D%0A      
-  %7D%0A  
+%7D%0A
       return t%5Bk
@@ -1362,17 +1362,16 @@
 %0A    %7D%0A%0A
-%0A
     priv
@@ -1407,26 +1407,24 @@
 es) %7B%0A      
-  
 int len = pr
@@ -1432,26 +1432,24 @@
 ces.length;%0A
-  
       int pr
@@ -1456,34 +1456,32 @@
 ofit = 0;%0A      
-  
 for (int i = 1; 
@@ -1504,20 +1504,16 @@
         
- 
-   
 // as lo
@@ -1558,20 +1558,16 @@
 profit.%0A
-    
         
@@ -1609,22 +1609,16 @@
         
-      
 profit +
@@ -1654,28 +1654,24 @@
         
-    
 %7D%0A      
   %7D%0A    
@@ -1658,30 +1658,26 @@
     %7D%0A      
-  %7D%0A  
+%7D%0A
       return
@@ -1691,11 +1691,14 @@
 ;%0A    %7D%0A
+  %7D
 %0A%7D%0A

refactor 188