題目：

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:

prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

鏈接：?http://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

題解：

股票題又來啦，這應(yīng)該是目前股票系列的最后一題。賣出之后有cooldown，然后求multi transaction的最大profit。第一印象就是dp，但每次dp的題目，轉(zhuǎn)移方程怎么也寫不好，一定要好好加強(qiáng)。出這道題的dietpepsi在discuss里也寫了他的思路和解法，大家都去看一看。不過我自己沒看懂....dp功力太差了， 反而是后面有一個(gè)哥們的state machine解法比較說得通。上面解法是based on一天只有一個(gè)操作，或買或賣或hold。也有一些理解為可以當(dāng)天買賣的解法，列在了discuss里。看來題目真的要指定得非常仔細(xì)，否則讀明白都很困難。

Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length == 0) {return 0;}int len = prices.length;int[] buy = new int[len + 1]; // before i, for any sequence last action at i is going to be buyint[] sell = new int[len + 1]; // before i, for any sequence last action at i is going to be sellint[] cooldown = new int[len + 1]; // before i, for any sequence last action at i is going to be cooldownbuy[0] = Integer.MIN_VALUE;for(int i = 1; i < len + 1; i++) {buy[i] = Math.max(buy[i - 1], cooldown[i - 1] - prices[i - 1]); // must sell to get profitsell[i] = Math.max(buy[i - 1] + prices[i - 1], sell[i - 1]);cooldown[i] = Math.max(sell[i - 1], Math.max(buy[i - 1], cooldown[i - 1]));}return Math.max(buy[len], Math.max(sell[len], cooldown[len]));} }

?

使用State machine的

public class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length < 2) {return 0;}int len = prices.length;int[] s0 = new int[len]; // to buyint[] s1 = new int[len]; // to sellint[] s2 = new int[len]; // to rests0[0] = 0;s1[0] = -prices[0];s2[0] = 0;for(int i = 1; i < len; i++) {s0[i] = Math.max(s0[i - 1], s2[i - 1]); s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);s2[i] = s1[i - 1] + prices[i];}return Math.max(s0[len - 1], s2[len - 1]); // hold and res } }

?

有機(jī)會還要簡化space complexity， 要看一看yavinci的解析。

?

題外話：

今天剛發(fā)現(xiàn)leetcode提交解答的頁面加上了題目號，方便了不少，以前只是總目錄有題號。 這題跟我的情況很像。現(xiàn)在公司的policy是買入股票必須hold 30天，而且不可以買地產(chǎn)類股票...我覺得自己也沒接觸什么數(shù)據(jù)，就做不了短線，真的很虧..

Reference:

https://leetcode.com/discuss/72030/share-my-dp-solution-by-state-machine-thinking

http://fujiaozhu.me/?p=725

http://bookshadow.com/weblog/2015/11/24/leetcode-best-time-to-buy-and-sell-stock-with-cooldown/

https://leetcode.com/discuss/71391/easiest-java-solution-with-explanations

http://www.cnblogs.com/grandyang/p/4997417.html

https://leetcode.com/discuss/71246/line-constant-space-complexity-solution-added-explanation

https://leetcode.com/discuss/73617/7-line-java-only-consider-sell-and-cooldown

https://leetcode.com/discuss/71354/share-my-thinking-process

總結(jié)

以上是生活随笔為你收集整理的309.Best Time to Buy and Sell Stock with Cooldown的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。