Skip to content

LeetCode: 309-Best Time to Buy and Sell Stock with Cooldown 解題紀錄

Last Updated on 2022-12-25 by Clay

題目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

  • After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

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

Example 1:

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

Example 2:

Input: prices = [1]
Output: 0

Constraints:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

題目給定一組數值陣列,陣列中的數值代表當天股票買賣的價格。如果在前一天已經賣過了股票,則不能在當前這一天買進股票;當已經買入股票沒有賣出的情況下,也不能再買進新的股票。


解題紀錄

DP

我們可以建立三組陣列 sellbuycooldown,初始值為 0、-1*第一天股價(代表第一天買入的情況)、0。

每個陣列代表著對應的行為,在當日操作時的最大效益。

  • sell:當日的最大效益為 max(sell[i-1], buy[i-1]+prices[i])
  • buy: 當日的最大效益為 max(buy[i-1], cooldown[i-1] - prices[i])
  • cooldown:當日的最大效益為 max(cooldown[i-1], sell[i-1])

最後,只需要返回 sell 的最後一項即可。


DP 複雜度

Time ComplexityO(n)
Space ComplexityO(n)


C++ 範例程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // Base case
        if (prices.size() == 1) {
            return 0;
        }

        // Init
        vector<int> sell({0});
        vector<int> buy({-1*prices[0]});
        vector<int> cooldown({0});

        // Filling
        for (int i=1; i<prices.size(); ++i) {
            sell.emplace_back(max(sell.back(), buy.back() + prices[i]));
            buy.emplace_back(max(buy.back(), cooldown.back() - prices[i]));
            cooldown.emplace_back(max(cooldown.back(), sell[i-1]));
        }

        return sell.back();
    }
};



Python 範例程式碼

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Base case
        if len(prices) == 1:
            return 0

        # Init
        sell = [0]
        buy = [-1 * prices[0]]
        cooldown = [0]

        # Filling
        for i in range(1, len(prices)):
            sell.append(max(sell[i-1], buy[i-1]+prices[i]))
            buy.append(max(buy[i-1], cooldown[i-1]-prices[i]))
            cooldown.append(max(cooldown[i-1], sell[i-1]))

        return sell[-1]

References


Read More

Leave a Reply