309 Best Time to Buy and Sell Stock with Cooldown 最佳買賣股票時機含冷凍期
Description:
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]
題目描述:
給定一個整數(shù)數(shù)組邪媳，其中第 i 個元素代表了第 i 天的股票價格 咙俩。?
設(shè)計一個算法計算出最大利潤金赦。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）斑粱。
賣出股票后捉貌，你無法在第二天買入股票 (即冷凍期為 1 天)传泊。
示例 :
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
思路:
動態(tài)規(guī)劃
dp[i][0]表示第 i天沒有股票的收益, dp[i][1]表示第 i天持有股票的收益
這里因為有冷卻期, 所以購買的時候要從前 2天開始
轉(zhuǎn)移方程:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i])
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
int maxProfit(vector<int>& prices)
{
int dp_i_0 = 0, dp_i_1 = INT_MIN, dp_pre_0 = 0;
for (int i = 0; i < prices.size(); i++)
{
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
};
Java:
class Solution {
public int maxProfit(int[] prices) {
int a = 0, b = Integer.MIN_VALUE, c = 0;
for (int i = 0; i < prices.length; i++) {
int t = a;
a = Math.max(a, b + prices[i]);
b = Math.max(b, c - prices[i]);
c = t;
}
return a;
}
}
Python:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
a, b, c = 0, -float('inf'), 0
for i in range(len(prices)):
a, b, c = max(a, b + prices[i]), max(b, c - prices[i]), a
return a
