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

在决定是否sell的时候,想到sell了之后要cool down,不能买进,所以global最优解可能并不是一直track local的最优解能得到的。例如[1,3,4,0,2],在3处sell了,0处还可以买进,总利润4。在4处sell,就不能再获得新的利润了,总利润是3. 所以比较明显用DP来做。

存什么样的中间结果呢?想到了三种transection各存一个array。这时,就应该放弃具体例子,写出三个transection各自的公式。
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])

注意到buy[i] <= rest[i], rest[i] <= sell[i],所以rest[i] = sell[i-1]. 所以公式变为:
buy[i] = max(sell[i-2] – price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s