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

what is the current day's k transactions profit, what is previous day's k-transactions profit. this it local k transactions profit, get the max of this IS global.

For each day i, [1..n], what is the maximal profit after j transaction, [1..k]

• at each day i, there will be a profit(or not, depends wether p[i] > p[i-1]) for transaction j, use a local array to keep track of transaction j's profit built along the days. local[j] = Math.max(global[j-1] + profit, local[j] + profit)
• update global profit.

public class Solution {
    public int maxProfit(int k, int[] prices) {
        int res = 0;
        if(prices == null || prices.length <=1 ) return res;
        if(k >= prices.length) return getAllProfit(prices);
        int[] local = new int[k+1];
        int[] global = new int[k+1]; // for each day i, transaction count is j, what is the maximal value.
        for(int i=1; i < prices.length; i++){
            int profit = prices[i] - prices[i-1];
            for(int j = k; j>=1 ; j--){
                local[j] = Math.max(global[j-1] + profit, local[j] + profit); // nothing to do with local[j-1];
                global[j] = Math.max(local[j], global[j]);
            }
        }

        return global[k];
    }

    int getAllProfit(int[] p){
        int res = 0;
        for(int i=1; i<p.length; i++){
            if(p[i] > p[i-1]){
                res += p[i] - p[i-1];
            }
        }
        return res;
    }
}