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

思路: dp[i][j] 表示在第i次交易和第j天交易时所能得到的最大利润，通过分析可知，dp[i][j]的值有两种可能性:

• 在第j天不进行交易, 此时最大利润表示为dp[i][j - 1]

• 在第j天进行交易，假设上一次交易的时间是第m天 (m = 0, 1, ...., j - 1)，则此时最大利润为 prices[j] - prices[m] + dp[i - 1][m]

所以要找出dp[i][j]的最大利润，我们只要找到在第m天里，使得我们能在第j天进行第i次交易时获得最大的利润profit，然后dp[i][j]等于profit和dp[i][j - 1]两者之间最大即可。最后返回的结果则是dp[k][prices.length - 1]

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++) {
            for (int j = 1; j < prices.length; j++) {
                int profit = 0;
                for (int m = j; m >= 0; m--) {
                    profit = Math.max(profit, prices[j] - prices[m] + dp[i - 1][m]);
                }
                dp[i][j] = Math.max(profit, dp[i][j - 1]);
            }
        }
        return dp[k][prices.length - 1];
    }

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

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

（2） DP优化

思路: 在第一种解法中, 我们要用两个for loop找到当我们在j天交易时可以获得最大利润，其中最里层的for loop是枚举上一次交易的第m(0 <= m < j)天，以获得price[j] - prices[m] + dp[i - 1][m]的最大值。其实这一步是可以合成一个for loop的，即只需要找到dp[i - 1][m] - prices[m]的最大值，记为maxDiff，那么我们每次在第j天交易时，只需要加上这个maxDiff就一定可以获得最大利润。

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 maxDiff = -prices[0];
            for (int j = 1; j < prices.length; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], prices[j] + maxDiff);
                maxDiff = Math.max(maxDiff, dp[i - 1][j] - prices[j]);
            }
        }
        return dp[k][prices.length - 1];
    }

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

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

3. Time & Space Complexity

DP: 时间复杂度O(k * n ^ 2), k是交易的次数, n是天数。 空间复杂度O(nk)

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