Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/309.html
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
Algorithm
Maintain three one-dimensional arrays buy, sell, and rest. among them:
buy[i] represents the maximum profit at this time when the last operation before the i day is buying.
sell[i] indicates that the last operation before the i-th day is selling, and the maximum profit at this time.
rest[i] indicates that the last operation before the i-th day is the freezing period, and the maximum profit at this time.
We write the recurrence formula as:
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])
The above recurrence is a good indication that there is a freezing period before buying, and the previous stocks must be sold before buying. A little trick is how to ensure that the situation of [buy, rest, buy] will not occur. This is because buy[i] <= rest[i], that is, rest[i] = max(sell[i-1], rest[ i-1]), which ensures that [buy, rest, buy] will not appear.
In addition, due to the existence of the freezing period, we can get rest[i] = sell[i-1]. In this way, we can reduce the above three recurrences to two:
buy[i] = max(sell[i-2]-price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
Code
-
public class Best_Time_to_Buy_and_Sell_Stock_with_Cooldown { class Solution_2D { public int maxProfit(int[] prices) { // buy[i]: Max profit till index i. The series of transaction is ending with a buy. // buy[i] = max(sell[i-2] - price, buy[i-1]) // sell[i]: Max profit till index i. The series of transaction is ending with a sell. // sell[i] = max(buy[i-1] + price, sell[i-1]) if (prices == null || prices.length == 0) { return 0; } int[] buy = new int[prices.length + 1]; // i is i-th day, not index int[] sell = new int[prices.length + 1]; buy[1] = -prices[0]; sell[1] = 0; // default for (int i = 2; i < prices.length + 1; i++) { buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i - 1]); // i-1去buy，还是i去buy sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i - 1]); // i-1去sell，还是i去sell } return sell[prices.length]; } } class Solution { public int maxProfit(int[] prices) { // buy[i]: Max profit till index i. The series of transaction is ending with a buy. // buy[i] = max(sell[i-2] - price, buy[i-1]) // sell[i]: Max profit till index i. The series of transaction is ending with a sell. // sell[i] = max(buy[i-1] + price, sell[i-1]) if (prices == null || prices.length == 0) { return 0; } int buy = Integer.MIN_VALUE; int pre_buy = 0; int sell = 0; int pre_sell = 0; for (int price : prices) { pre_buy = buy; buy = Math.max(pre_sell - price, pre_buy); pre_sell = sell; sell = Math.max(pre_buy + price, pre_sell); } return sell; } } } ############ class Solution { public int maxProfit(int[] prices) { int f1 = -prices[0], f2 = 0, f3 = 0; for (int i = 1; i < prices.length; ++i) { int pf1 = f1, pf2 = f2, pf3 = f3; f1 = Math.max(pf1, pf3 - prices[i]); f2 = Math.max(pf2, pf1 + prices[i]); f3 = Math.max(pf3, pf2); } return f2; } } -
// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ // Time: O(N) // Space: O(N) class Solution { public: int maxProfit(vector<int>& A) { if (A.empty()) return 0; int N = A.size(), buy = INT_MIN; vector<int> dp(N + 1, 0); for (int i = 0; i < N; ++i) { buy = max(buy, (i >= 1 ? dp[i - 1] : 0) - A[i]); dp[i + 1] = max(dp[i], buy + A[i]); } return dp[N]; } }; -
class Solution: def maxProfit(self, prices: List[int]) -> int: f1, f2, f3 = -prices[0], 0, 0 for price in prices[1:]: pf1, pf2, pf3 = f1, f2, f3 f1 = max(pf1, pf3 - price) f2 = max(pf2, pf1 + price) f3 = max(pf3, pf2) return f2 ############ class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ if len(prices) < 2: return 0 buy = [0] * len(prices) sell = [0] * len(prices) buy[0] = -prices[0] buy[1] = max(-prices[1], buy[0]) sell[0] = 0 sell[1] = max(prices[1] - prices[0], 0) for i in range(2, len(prices)): buy[i] = max(sell[i - 2] - prices[i], buy[i - 1]) sell[i] = max(prices[i] + buy[i - 1], sell[i - 1]) return max(sell) -
func maxProfit(prices []int) int { f1, f2, f3 := -prices[0], 0, 0 for i := 1; i < len(prices); i++ { pf1, pf2, pf3 := f1, f2, f3 f1 = max(pf1, pf3-prices[i]) f2 = max(pf2, pf1+prices[i]) f3 = max(pf3, pf2) } return f2 } func max(a, b int) int { if a > b { return a } return b } -
function maxProfit(prices: number[]): number { const n = prices.length; let dp = Array.from({ length: n }, v => new Array(3).fill(0)); dp[0] = [0, -prices[0], Number.MIN_SAFE_INTEGER]; for (let i = 1; i < n; i++) { dp[i] = [ Math.max(dp[i - 1][0], dp[i - 1][2]), Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]), dp[i - 1][1] + prices[i], ]; } return Math.max(dp[n - 1][0], dp[n - 1][2]); }