Last Updated on 2022-12-25 by Clay
題目
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
- After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1] Output: 0
Constraints:
1 <= prices.length <= 50000 <= prices[i] <= 1000
題目給定一組數值陣列，陣列中的數值代表當天股票買賣的價格。如果在前一天已經賣過了股票，則不能在當前這一天買進股票；當已經買入股票沒有賣出的情況下，也不能再買進新的股票。
解題紀錄
DP
我們可以建立三組陣列 sell、buy、cooldown，初始值為 0、-1*第一天股價（代表第一天買入的情況）、0。
每個陣列代表著對應的行為，在當日操作時的最大效益。
sell：當日的最大效益為max(sell[i-1], buy[i-1]+prices[i])buy： 當日的最大效益為max(buy[i-1], cooldown[i-1] - prices[i])cooldown：當日的最大效益為max(cooldown[i-1], sell[i-1])
最後，只需要返回 sell 的最後一項即可。
DP 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(n) |
C++ 範例程式碼
class Solution {
public:
int maxProfit(vector<int>& prices) {
// Base case
if (prices.size() == 1) {
return 0;
}
// Init
vector<int> sell({0});
vector<int> buy({-1*prices[0]});
vector<int> cooldown({0});
// Filling
for (int i=1; i<prices.size(); ++i) {
sell.emplace_back(max(sell.back(), buy.back() + prices[i]));
buy.emplace_back(max(buy.back(), cooldown.back() - prices[i]));
cooldown.emplace_back(max(cooldown.back(), sell[i-1]));
}
return sell.back();
}
};Python 範例程式碼
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Base case
if len(prices) == 1:
return 0
# Init
sell = [0]
buy = [-1 * prices[0]]
cooldown = [0]
# Filling
for i in range(1, len(prices)):
sell.append(max(sell[i-1], buy[i-1]+prices[i]))
buy.append(max(buy[i-1], cooldown[i-1]-prices[i]))
cooldown.append(max(cooldown[i-1], sell[i-1]))
return sell[-1]