188. Best Time to Buy and Sell Stock IV

This problem is similar to 123. Best Time to Buy and Sell Stock III. The previous problem define we can only make at most two transactions. In this problem, we can make at most k transactions.

Similarly, we define two array sell and hold to record maximum profit where sell[i] is the maximum profit after selling stock i times and hold[i] is the maximum profit after buying stock i times. Since we can only hold at most one stock at the same time, we can make at most prices.length / 2 transactions. The length of sell and hold is max(k, prices.length / 2) + 1 (If we don't compare k and prices.length / 2, MLE will occur).

Note that we should initiate elements in hold to Integer.MIN_VALUE (If we set hold[i] to zero, we won't get correct answer).

public int maxProfit(int k, int[] prices) {
    int length = Math.min(k, prices.length / 2) + 1;
    int sell[] = new int[length];
    int hold[] = new int[length];
    for(int i = 0; i < length; i++)
	hold[i] = Integer.MIN_VALUE;
    for(int i = 0; i < prices.length; i++) {
	for(int j = length - 1; j >= 1; j--) {
	    sell[j] = Math.max(sell[j], hold[j] + prices[i]);
	    hold[j] = Math.max(hold[j], sell[j - 1] - prices[i]);
	}
    }
    return sell[length - 1];
}