309.Best Time to Buy and Sell Stock with Cooldown
Tags: [dp], [two_memo_dp], [stock]
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/\#/description
Say you have an array for which theithelement is the price of a given stock on dayi.
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:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
Solution: DP, Two Memo DP
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices) < 2:
return 0
num_of_days = len(prices)
# buy[i] is the max profit we can get in the day range[0, i],
# and the last operation in the transaction series is 'buy',
# this 'buy' operation can happen on day i, i - 1, i - 2, ...
# but it must be the last operation in the series.
buy = [0 for _ in xrange(num_of_days)]
# sell[i] is the max profit we can get in the day range[0, i],
# and the last operation in the transaction series is 'sell',
# this 'sell' operation can happend on day i, i - 1, i - 2, ...
# but it must be the last operatioin in the series.
sell = [0 for _ in xrange(num_of_days)]
# For buy[i],
# (1) On day i, we choose to do nothing, the max profit depends on buy[i - 1].
# (2) On day i, we choose to buy, but before we buy, there are two cases:
# (i) There is no transactions in the day range[0, i - 1], which is represented by (- prices[i]).
# (ii) There is transactions in the day range[0, i - 1],
# and the last operation is 'sell' in the day range[0, i - 1],
# which is represented by sell[i - 1].
# But becasue there is 'cooldown' which means if we want to buy on day i, we cannot sell it on day (i - 1),
# so we can use sell[i - 2] to guarantee the last 'sell' operation happened in day[0, i - 2],
# not on day (i - 1).
# So there are three cases.
# So buy[i] = max(buy[i - 1], (sell[i - 2] - prices[i]), (-prices[i])).
# The reason why we "- prices[i]", because we buy the stock, we need pay money (prices[i]).
# For sell[i],
# (1) On day i, we choose to do nothing, the max profit depends on sell[i - 1].
# (2) On day i, we choose to sell the stock. Because we want to sell stock on day i,
# so before we sell it we must buy it first on day[0, i - 1].
# So sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]).
# The reason here we use '+ prices[i]' because during the buy[i - 1] we have already paid the money when we bought it.
# Now we just need to add our gettings. So (buy[i - 1] + prices[i]) will contains the profit from this transaction.
# In short:
# buy[i] = max(buy[i - 1], (sell[i - 2] - prices[i]), (-prices[i]))
# sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
# For day 0,
# buy[0] = -prices[0], buy[0] means on day [0, 0] the transaction series must be ended with 'buy'.
# sell[0] = -prices[0] + prices[0], means the first we buy it and at the same day we sell it.
buy[0] = -prices[0]
sell[0] = -prices[0] + prices[0]
# For day 1,
# buy[1] = max((buy it on day 0), (buy it on day 1)).
# sell[1] = max(sell[0], (buy it on day 0, then sell it on day 1)).
buy[1] = max(buy[0], -prices[1])
sell[1] = max(sell[0], buy[0] + prices[1])
for i in xrange(2, num_of_days):
buy[i] = max(buy[i - 1], (sell[i - 2] - prices[i]), (-prices[i]))
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])
# Finally we just need return max(0, sell[num_of_days - 1]).
# Because the transaction series can be ended by two cases:
# (1) There is no transactions happened at all during the day[0, i], the profit is 0.
# (2) There are some transactions happened, but the last operation must be 'sell', which make sense,
# we don't want to the transaction series ended by 'buy', which must get less profit than ending with 'sell'.
return max(0, sell[num_of_days - 1])
Revelation:
- See comments in the code.
- Here the stock can be bought and sold at the same day.
Note:
- Time complexity = O(n), n is the number of elements in prices.
- Space complexity = O(n), n is the number of elements in prices.
Time Limited Exceeded:
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices) < 2:
return 0
return self.max_profit_helper(prices, 0, -1, -1, 0)
def max_profit_helper(self, prices, index, bought_date, sold_date, curr_profit):
# base case
if index >= len(prices):
return curr_profit
max_profit = 0
for i in xrange(index, len(prices)):
if bought_date >= 0:
# we have bought this stock at bought_date
# we can choose to sell it
max_profit = max(max_profit,
self.max_profit_helper(prices, i + 1, -1, i, curr_profit + (prices[i] - prices[bought_date])))
# we can choose not to sell it
max_profit = max(max_profit,
self.max_profit_helper(prices, i + 1, bought_date, -1, curr_profit))
else:
# we didn't buy stock,
# we may have sold it, or we may never bought it.
if not (sold_date >= 0 and sold_date == i - 1):
# we can choose to buy it.
max_profit = max(max_profit,
self.max_profit_helper(prices, i + 1, i, -1, curr_profit))
# we do not buy it
max_profit = max(max_profit,
self.max_profit_helper(prices, i + 1, -1, sold_date, curr_profit))
return max_profit
Revelation:
- Try all possible ways to operate the stock.
- See comments in the code
Note:
- Time complexity = O(n!), n is the number of elements of prices.