Question

Formatted question description: https://leetcode.ca/all/309.html

 309. Best Time to Buy and Sell Stock with Cooldown 无限次交易但是卖掉之后的第一天不能买

 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:

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

 @tag-array

Algorithm

Maintain three one-dimensional arrays buy, sell, and rest. among them:

buy[i] represents the maximum profit at this time when the last operation before the i day is buying.

sell[i] indicates that the last operation before the i-th day is selling, and the maximum profit at this time.

rest[i] indicates that the last operation before the i-th day is the freezing period, and the maximum profit at this time.

We write the recurrence formula as:

buy[i] = max(rest[i-1]-price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

The above recurrence is a good indication that there is a freezing period before buying, and the previous stocks must be sold before buying. A little trick is how to ensure that the situation of [buy, rest, buy] will not occur. This is because buy[i] <= rest[i], that is, rest[i] = max(sell[i-1], rest[ i-1]), which ensures that [buy, rest, buy] will not appear.

In addition, due to the existence of the freezing period, we can get rest[i] = sell[i-1]. In this way, we can reduce the above three recurrences to two:

buy[i] = max(sell[i-2]-price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])

Code

Java

  • /**
    
    
     */
    
    public class Best_Time_to_Buy_and_Sell_Stock_with_Cooldown {
    
        class Solution_2D {
            public int maxProfit(int[] prices) {
    
                // buy[i]: Max profit till index i. The series of transaction is ending with a buy.
                //      buy[i]  = max(sell[i-2] - price, buy[i-1])
                // sell[i]: Max profit till index i. The series of transaction is ending with a sell.
                //      sell[i] = max(buy[i-1] + price, sell[i-1])
    
                if (prices == null || prices.length == 0) {
                    return 0;
                }
    
                int[] buy = new int[prices.length + 1]; // i is i-th day, not index
                int[] sell = new int[prices.length + 1];
    
                buy[1] = -prices[0];
                sell[1] = 0; // default
    
                for (int i = 2; i < prices.length + 1; i++) {
                    buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i - 1]); // i-1去buy,还是i去buy
                    sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i - 1]); // i-1去sell,还是i去sell
                }
    
                return sell[prices.length];
            }
        }
    
        class Solution {
            public int maxProfit(int[] prices) {
    
                // buy[i]: Max profit till index i. The series of transaction is ending with a buy.
                //      buy[i]  = max(sell[i-2] - price, buy[i-1])
                // sell[i]: Max profit till index i. The series of transaction is ending with a sell.
                //      sell[i] = max(buy[i-1] + price, sell[i-1])
    
                if (prices == null || prices.length == 0) {
                    return 0;
                }
    
                int buy = Integer.MIN_VALUE;
                int pre_buy = 0;
                int sell = 0;
                int pre_sell = 0;
                for (int price : prices) {
                    pre_buy = buy;
                    buy = Math.max(pre_sell - price, pre_buy);
                    pre_sell = sell;
                    sell = Math.max(pre_buy + price, pre_sell);
                }
    
                return sell;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int maxProfit(vector<int>& A) {
            if (A.empty()) return 0;
            int N = A.size(), buy = INT_MIN;
            vector<int> dp(N + 1, 0);
            for (int i = 0; i < N; ++i) {
                buy = max(buy, (i >= 1 ? dp[i - 1] : 0) - A[i]);
                dp[i + 1] = max(dp[i], buy + A[i]);
            }
            return dp[N];
        }
    };
    
  • class Solution(object):
      def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2:
          return 0
        buy = [0] * len(prices)
        sell = [0] * len(prices)
        buy[0] = -prices[0]
        buy[1] = max(-prices[1], buy[0])
        sell[0] = 0
        sell[1] = max(prices[1] - prices[0], 0)
        for i in range(2, len(prices)):
          buy[i] = max(sell[i - 2] - prices[i], buy[i - 1])
          sell[i] = max(prices[i] + buy[i - 1], sell[i - 1])
        return max(sell)
    
    

All Problems

All Solutions