Best Time to Buy and Sell Stock with Cooldown (M)
題目
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]
題意
股票買賣問題，給定每一天的股票價格以及相應規則：同一天只能買或賣，賣股票必須在買股票之后，可以執行多次買賣交易，但每次賣股票后隔一天才能再次買股票，要求計算能得到的最大利潤，
思路
動態規劃，定義兩個陣列：
- \(hold[i]\) 表示在第i天手頭上仍有股票未出售時已經得到的最大利潤
- \(sold[i]\) 表示在第i天未持有任何股票時已經得到的最大利潤
對于\(hold[i]\)，有兩種情況導致第i天仍持有股票：
- 恰好在第i天購入股票，因為冷卻時間的存在，必須在第i-2天或之前就賣掉上一個持有的股票；
- 在第i-1天或之前就已經持有了股票，而在第i天沒有做任何事，
對于\(sold[i]\)，同樣有兩種情況導致第i天手頭沒有股票：
- 恰好在第i天賣掉了股票；
- 在第i-1天或之前就已經賣掉了股票，而在第i天沒有做任何事，
綜合以上可以得到兩個遞推公式：
\[\begin{cases} hold[i]=max(sold[i-2]-prices[i],\ hold[i-1])\\\\ sold[i]=max(hold[i-1]+prices[i],\ sold[i-1]) \end{cases} \]
代碼實作
Java
class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
int[] hold = new int[prices.length];
int[] sold = new int[prices.length];
hold[0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
hold[i] = Math.max(i == 1 ? -prices[1] : sold[i - 2] - prices[i], hold[i - 1]);
sold[i] = Math.max(hold[i - 1] + prices[i], sold[i - 1]);
}
return sold[sold.length - 1];
}
}
參考
【LeetCode】309. Best Time to Buy and Sell Stock with Cooldown 解題報告（Python & C++）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10650.html
標籤：其他
上一篇：樹狀陣列1
下一篇：劍指offer-剪繩子1