LeetCode Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the i^th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

1. sells[i]=max(buys[i-1]+prices[i], sells[i-1]+profit)
2. buys[i]=max(sells[i-2]-prices[i], buys[i-1]-profit)

1. 第i天卖出的收益=max(第i-1天买入+第i天卖出的收益，第i-1天卖出~但反悔了~改为第i天卖出)
2. 第i天买入的收益=max(第i-2天卖出~第i-1天冷却~第i天买入的负收益，第i-1天买入~但反悔了~改为第i天买入)

1. 第i-1天卖出后反悔，改为第i天卖出 等价于 第i-1天持有股票，第i天再卖出
2. 第i-1天买入后反悔，改为第i天买入 等价于 第i-1天没有股票，第i天再买入

188. Best Time to Buy and Sell Stock IV

Say you have an array for which the i-th 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.

这是股票买卖最难的一题！问最多进行k次交易能获得的最大收益是多少。参考网上题解1和题解2。 令mustSell[i][j]表示前i天最多交易j次能获得的最大收益，且第i天必须卖出；globalBest[i][j]表示前i天最多交易j次能获得的最大收益，不要求第i天必须卖出。则有如下递推关系：

1. mustSell[i][j]=max(globalBest[i-1][j-1]+profit, mustSell[i-1][j]+profit)
2. globalBest[i][j]=max(globalBest[i-1][j], mustSell[i][j])

解释一下，profit=prices[i]-prices[i-1]为第i-1天买入，第i天卖出的收益。

第一个公式中，前i天最多交易j次且第i天卖出的最大收益为“前i-1天最多交易j-1次的全局最大收益+第i-1天买入第i天卖出的收益”与“前i-1天最多交易j次且第i-1天卖出的最大收益+第i-1天买入第i天卖出的收益”的较大者。第一部分好理解，第二部分为什么还是j次交易呢，第一眼看上去好像有j+1次交易了，但是因为mustSell[i-1][j]表示第i-1天必须卖出，而profit表示第i-1天要买入，第i天卖出，两者加起来的效果相当于第i-1天的卖出买入抵消了，即交易次数还是j次，而且恰好变成了第i天卖出，和mustSell[i][j]的含义一致。

第二个公式就好理解了，前i天最多交易j次的全局最大收益为“最后一次交易不在第i天发生，则globalBest[i-1][j]”与“最后一次交易在第i天发生，则mustSell[i][j]”的较大者。
如果允许交易的次数k很大，那么以上DP效率较低，可以换成LeetCode Best Time to Buy and Sell Stock II的贪心策略。因为一次交易至少涉及到两天，所以如果k>=prices.size()/2时，可以采用贪心策略。

完整代码如下：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices)
    {
        int days = prices.size();
        if (days < 2)
            return 0;
        if (k >= days / 2) {
            int ans = 0;
            for (int i = 1; i < days; ++i) {
                if (prices[i] > prices[i – 1])
                    ans += (prices[i] – prices[i – 1]);
            }
            return ans;
        }
        vector<vector<int> > mustSell(days, vector<int>(k + 1, 0)), globalBest(days, vector<int>(k + 1, 0));
        for (int i = 1; i < days; ++i) {
            int profit = prices[i] – prices[i – 1];
            for (int j = 1; j <= k; ++j) {
                mustSell[i][j] = max(globalBest[i – 1][j – 1] + profit, mustSell[i – 1][j] + profit);
                globalBest[i][j] = max(globalBest[i – 1][j], mustSell[i][j]);
            }
        }
        return globalBest[days – 1][k];
    }
};

本代码提交AC，用时9MS。

123. Best Time to Buy and Sell Stock III

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

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

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

股票买卖题三。这次限制最多交易两次，问最大能获利多少。这确实是个hard题，研一卜神算法作业中遇到过。 先来回顾一下股票买卖第一题LeetCode Best Time to Buy and Sell Stock，当时的做法是从左往右找到除了当前值的最小值min_so_far，然后用当前值减去min_so_far，表示如果在当前卖出（即用min_so_far买入）能获得的最大收益profit1。这一题允许最多两次交易，那么如果求到在当前买入能获得的最大收益profit2，则profit1+profit2表示在当前卖出后买入能获得的最大收益。计算所有的profit1+profit2的最大值，就是两次交易能获得的最大收益。 计算profit2的方法和计算profit1类似，此时我们从右往左找到除了当前值的最大值max_so_far，则用max_so_far减去当前值，就表示在当前买入（max_so_far卖出）能获得的最大收益profit2。

整理一下思路：我们尝试把每个点作为两次交易的分界点，那么这个点在上一个交易中卖出了，同时在下一个交易中买入了，我们要分别求到在这个点卖出和买入能获得的最大收益，然后把两个值加起来就是在这个点两次交易的最大收益。求所有点的最大收益的最大值就是最终结果。 举个例子，如下表，表中的min_so_far和profit1是从左往右计算的，max_so_far和profit2是从右往左计算的，profit1/2计算的都是当前profit和历史profit的最大值，和代码中的含义一致。

完整代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        if (n < 2)
            return 0;
        vector<int> minprice(n), maxprice(n);
        for (int i = 0; i < n; ++i) {
            minprice[i] = i == 0 ? INT_MAX : min(minprice[i – 1], prices[i – 1]);
            maxprice[n – i – 1] = i == 0 ? INT_MIN : max(maxprice[n – i], prices[n – i]);
        }
        vector<int> profit1(n), profit2(n);
        for (int i = 0; i < n; ++i) {
            profit1[i] = i == 0 ? 0 : max(profit1[i – 1], prices[i] – minprice[i]);
            profit2[n – i – 1] = i == 0 ? 0 : max(profit2[n – i], maxprice[n – i – 1] – prices[n – i – 1]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, profit1[i] + profit2[i]);
        }
        return ans;
    }
};

本代码提交AC，用时9MS。

二刷。类似的代码，或许更好理解：

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int n = prices.size();
		if (n == 0 || n == 1)return 0;
		vector<int> cur_min(n, INT_MAX), cur_max(n, INT_MIN);
		cur_min[0] = prices[0];
		cur_max[n - 1] = prices[n - 1];
		for (int i = 1; i < n; ++i) {
			cur_min[i] = min(cur_min[i - 1], prices[i]);
			cur_max[n - i - 1] = max(cur_max[n - i], prices[n - i - 1]);
		}
		vector<int> dp_sell(n, 0), dp_buy(n, 0);
		for (int i = 1; i < n; ++i) {
			dp_sell[i] = max(dp_sell[i - 1], prices[i] - cur_min[i]);
			dp_buy[n - i - 1] = max(dp_buy[n - i], cur_max[n - i - 1] - prices[n - i - 1]);
		}
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans = max(ans, dp_sell[i] + dp_buy[i]);
		}
		return ans;
	}
};

本代码提交AC，用时16MS。

121. Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

股票买卖问题。给定股票每天的价格，问哪天买入和哪天卖出能获得最大收益。动态规划问题，本科就遇到过了。之前一贯的做法是这样的：要使prices[j]-prices[i]的差值最大，因为prices[j]-prices[i]=(prices[j]-prices[j-1])+(prices[j-1]-prices[j-2])+…+(prices[i+1]-prices[i])，等式右边的每一项就是相邻两天的股价差。所以我们可以对每相邻两天的股价做差，得到一个新的n-1长的数组diff，然后对diff求最大连续子串和。最大连续子串和又可以用DP解决，令dp[i]为包含diff[i]的最大连续子串和，如果dp[i-1]>0，则dp[i]=dp[i-1]+diff[i]；否则dp[i]=diff[i]。最后dp数组的最大值即为最大收益。
这种思路的代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        if (prices.size() < 2)
            return 0;
        vector<int> diff(prices.size() – 1);
        for (int i = 1; i < prices.size(); ++i) {
            diff[i – 1] = prices[i] – prices[i – 1];
        }
        vector<int> dp(diff.size());
        int ans = 0;
        for (int i = 0; i < diff.size(); ++i) {
            if (i == 0 || dp[i – 1] < 0)
                dp[i] = diff[i];
            else
                dp[i] = dp[i – 1] + diff[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

本代码提交AC，用时9MS。
还可以对上述思路简化，我们记录当前遇到的最小值min_so_far，那么如果第i天卖出的话，最大的收益就是prices[i]-min_so_far了，所以我们用dp[i]记录第i天卖出的最大收益。最后对dp数组求最大值，即为最大收益。
这种思路的代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        if (prices.size() < 2)
            return 0;
        vector<int> dp(prices.size());
        int min_so_far = prices[0], ans = 0;
        for (int i = 1; i < prices.size(); ++i) {
            dp[i] = prices[i] – min_so_far;
            min_so_far = min(min_so_far, prices[i]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

本代码提交AC，用时6MS。
还有一种解法，用minprice和maxprice分别记录从左往右当前的最小值和从右往左当前的最大值，最大收益就是用maxprice-minprice的最大值。完整代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int n = prices.size();
        if (n < 2)
            return 0;
        vector<int> minprice(n), maxprice(n);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            minprice[i] = (i == 0 ? prices[0] : min(minprice[i – 1], prices[i]));
            maxprice[n – i – 1] = (i == 0 ? prices[n – 1] : max(maxprice[n – i], prices[n – i – 1]));
        }
        for (int i = 0; i < n; ++i) {
            ans = max(ans, maxprice[i] – minprice[i]);
        }
        return ans;
    }
};

本代码提交AC，用时9MS。