# 188     Best Time to Buy and Sell Stock IV

## 188. [Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/)

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

**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]

```java
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就一定可以获得最大利润。

```java
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)