188. Best Time to Buy and Sell Stock IV - jiejackyzhang/leetcode-note GitHub Wiki

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

解题思路为Dynamic Programming。

一个技巧是如果k>=len/2，则这个问题转化为任意transaction的问题。

general情形下采用DP的解法，是"123. Best Time to Buy and Sell Stock III"的general case。

令dp[i][j]表示最多i次transaction，时间到j的max profit。 tmpMax表示时间到j，状态是buy的max profit。

则：

dp[i][j] = max(dp[i][j-1], prices[j]+tmpMax)
tmpMax = max(tmpMax, dp[i-1][j]-prices[j])

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length <= 1) return 0;
        int n = prices.length;
        if(k >= n/2) return quickSolve(prices);
        int[][] dp = new int[k+1][n];
        for(int i = 1; i <= k; i++) {
            int tmpMax = dp[i-1][0] - prices[0];
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + tmpMax);
                tmpMax = Math.max(tmpMax, dp[i-1][j] - prices[j]);
            }
        }
        return dp[k][n-1];
    }
    
    private int quickSolve(int[] prices) {
        int maxProfit = 0;
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] > prices[i-1]) {
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }
}