package code;
/*
 * 188. Best Time to Buy and Sell Stock IV
 * k
 * Hard
 * Dynamic Programming
 * dp, dp[i][j] iprices[0~j]
 *      dp[i][j] = Max( dp[i][j-1], dp[i-1][jj]+prices[j]-prices[jj] )   { jj in range of [0, j-1] }
 *               = Max( dp[i][j-1], prices[j]+ max(dp[i-1][jj]-prices[jj]) ) 
 *      dp[0][j] = 0;  dp[i][0] = 0;
 * Tipslc121, lc309, lc188, lc123, lc714
 */
public class lc188 {
    public int maxProfit(int k, int[] prices) {
        if(prices.length==0) return 0;
        int n = prices.length;
        //if k >= n/2, then you can make maximum number of transactions.
        if (k >=  n/2) {
            int maxPro = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i-1])
                    maxPro += prices[i] - prices[i-1];
            }
            return maxPro;
        }

        int[][] dp = new int[k+1][prices.length];
        for (int i = 1; i