188. Best Time to Buy and Sell Stock IV

题目描述

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

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.

解题思路

跟之前做过的买股票的问题类似，但是区别在于，这次买卖股票不需要交付手续费，也就是说，同一天内可以同时买和卖股票，即：

考虑数组[1,2,4]，k暂时不做限制。最大的利润是：(2-1) + (4-2) = 3。跟之前的题目不同，由于没有了手续费，同一天内卖买股票不会造成亏损。当k没有限制，那么这道题实际上就是找到这个数组的所有递增序列，并且把它们之间的差值相加，就可以得到正确答案。

考虑数组[1,0,2,3,1,0,4]，递增子序列有0,2,3和0,4，利润最大值是(2-0)+(3-2)+(4-0)=7。为什么能这样做呢？

当我们考虑购入股票a[i]时，如果它不在递增子序列中，那么我一定能找到a[k] < a[i]，k > i，让购入成本更低。由题目我们可以知道，当手上拥有股票的时候是没有办法买入的，因此，要获得收益，就不能在递减序列中买入，因为后面一定会有更低的购入成本。

当我们购入的a[i]在递增序列中时，我们选择在a[i+1]时将它出售，并买入a[i+1]。假设这个递增序列长为n+1，那么它的最小值为a[i]，最大值为a[i+n]，获得的收益为:
(a[i+1] - a[i])+(a[i+2] - a[i+1]) + ... + (a[i+n] - a[i+n-1]) = a[i+n] - a[i]
即在最高价卖出最低价买入，显然为这个递增子序列的最大利润值

很显然，且k的大小大于数组长度的一半时（一次交易是指买入+卖出），我们就可以用这样的方式不断的找递增序列，然后算出最大利润值。

但是，如果k的值没有那么大呢？这时候就要用到动归的思路了。状态转移基本和之前一致，但需要加上交易次数的约束:

dp[i][j][0]表示在第i天，总交易次数为j次的情况下，不持有股票的最大收益
dp[i][j][1]表示在第i天，总交易次数为j次的情况下，持有股票的最大收益
/*第j次卖出的股票应该是第j次买入的股票*/
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
/*第j次买入股票时的状态应该是第j-1次卖出时的状态*/
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
在这里j是要小于等于k的

当然，这里也可以用到上次用过的状态压缩，将dp三维数组变成两个一维数组（即2维空间）。由于我们对前一天的状态并不关心，因此只需要不断进行状态更迭即可。同时，这里依然要注意循环迭代顺序的问题。由于第j次交易的信息是依赖于第j-1次交易信息的，因此，我们还是要从后往前更迭。

noStock[j]]代表第j次抛出股票后的获得最大收益
holdStock[j]代表第j次持有股票时的最大收益
/*保持昨天不持有股票时第j次交易的利润，或者抛售昨天持有的股票，注意这里是hold[j]表示已经购买了j次股票*/
noStock[j] = max(noStock[j], hold[j]+prices[i])
/*保持昨天持有股票时第j次交易的利润，或者买入今天的股票，noStock[j-1]代表之前只交易了j-1次，这次购买为第j次*/
holdStock[j] = max(holdStock[j], noStock[j-1] - prices[i])

至此，这个问题的算法就算是比较清晰了。

一点小坑

看了后面讲的动态规划算法之后，是不是觉得之前分析的，不考虑k的算法没有用呢？当然不是！在测试数据中，数组并不会给的非常长，但是，交易次数k却可以设一个很大的阈值。这时候再开出长度为k+1的数组，很容易出现栈溢出的错误。这时，我们就可以用到之前的判断条件，找其递增子序列即可。

时间复杂度分析

遍历数组中的每一个元素，遍历背包中的不同容量：O(n*k)

空间复杂度分析

O(k)

源码

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() < 2) {
            return 0;
        }
        if (k > prices.size() / 2) {
            int max_ = 0;
            for (int i = 1; i < prices.size(); ++i) {
                max_ += max(prices[i] - prices[i-1], 0);
            }
            return max_;
        }
        int days = prices.size();
        int dp[days][k+1][2];
        for (int i = 0; i < days; ++i) {
            for (int j = 0; j < k + 1; ++j) {
                for (int q = 0; q < 2; ++q) {
                    dp[i][j][q] = 0;
                }
            }
        }
        for (int i = 0; i <= k; ++i) {
            dp[0][i][1] = -prices[0];
        }
        for (int i = 1; i < days; ++i) {
            for (int j = 1; j <= k; ++j) {
                // no-stock
                int temp = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][0] = temp;
                // have-stock
                int temp2 = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
                dp[i][j][1] = temp2;
            }
        }
        int max = -99999;
        for (int i = 0; i <= k; ++i) {
            if (max < dp[days-1][i][0]) {
                max = dp[days-1][i][0];
            }
        }
        return max;
    }
};