188 Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV

1. Question

Say you have an array for which theithelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete at mostktransactions.

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

Example 1:

Input: [2,4,1], k = 2

Output: 2

Explanation:
Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2

Output: 7

Explanation:
Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

2. Implementation

(1) DP

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        if (k >= prices.length / 2) {
            return maxProfitWithUnlimitedTransactions(prices);
        }

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

        for (int i = 1; i <= k; i++) {
            int holding = -prices[0];
            for (int j = 1; j < prices.length; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], holding + prices[j]);
                holding = Math.max(holding, dp[i - 1][j - 1] - prices[j]);
            }
        }
        return dp[k][prices.length - 1];
    }

    public int maxProfitWithUnlimitedTransactions(int[] prices) {
        int curMax = 0;
        int max = 0;

        for (int i = 1; i < prices.length; i++) {
            curMax = prices[i] > prices[i - 1] ?  curMax + prices[i] - prices[i - 1] : curMax;
            max = Math.max(max, curMax);
        }
        return max;
    }
}

3. Time & Space Complexity

DP: 时间复杂度O(nk), 空间复杂度O(nk)