leetcode-309-Best Time to Buy and Sell Stock with Cooldown

Posted on | In , | |
Words count in article: 601 | Reading time ≈ 3

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

Example:

1
2
3
Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

首先，我们看到问题中提到了三种状态buy、sell和cooldown，那么我们脑中的第一个想法就是通过动态规划来解

如果我们index:i天为冷冻期，那么只能说明index:i-1天卖掉了股票，那么i天的收益和i-1天是一样的

cooldown[i]=sell[i-1]
如果我们考虑index:i天卖出，要求利润最大的话。那么无非是index:i-1之前就持有股票，所以index:i-1天也可以卖出，或者另一种情况就是index:i-1当天买入了股票。

sell[i]=max(sell[i-1], buy[i-1]+prices[i])
如果我们考虑index:i天买入，要求利润最大的话。无非是index:i-1之前就不持有股票，我们要考虑哪天买，所以index:i-1也可以买入，或者另一种可能就是index:i-1天是冷冻期。

buy[i]=max(buy[i-1], cooldown[i-1]-prices[i])
我们第一天不可能卖出或者冻结，那么这两个sell[0]=0 cooldown[0]=0，但是我们第一天可以买入啊，所以buy[0]=-prices[0]。还有一点要注意的就是，我们一定是最后一天卖出或者最后一天冻结利润最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (!prices.size()) 
            return 0;
        vector<int> buy(prices.size(), 0), sell(prices.size(), 0), cooldown(prices.size(), 0);
        buy[0] = -prices[0];
        for (unsigned int i = 1; i < prices.size(); ++i)
        {
            cooldown[i] = sell[i - 1];
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = max(buy[i - 1], cooldown[i - 1] - prices[i]);
        }
        return max(sell[prices.size() - 1], cooldown[prices.size() - 1]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0)
            return 0;
        int[] buy = new int[prices.length];
        int[] sell = new int[prices.length];
        int[] cooldown = new int[prices.length];
        buy[0] =  -prices[0];
        for(int i=1; i<prices.length; i++)
        {
            cooldown[i] = sell[i-1];
            sell[i] = Math.max(sell[i-1], buy[i-1]+prices[i]);
            buy[i] = Math.max(buy[i-1], cooldown[i-1]-prices[i]);
        }
        return Math.max(cooldown[prices.length-1], sell[prices.length-1]);
    }
}
Donate? comment?