309. Best Time to Buy and Sell Stock with Cooldown
T: O(n)
S: O(1)
```java
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int hasStock = -prices[0]; // has stock
int sold = 0; // sold
int cooled = 0; // cooled
for (int i = 1; i < n; i++) {
int hasStock2 = hasStock;
int sold2 = sold;
int cooled2 = cooled;
// buy sell cooldown buy sell, so hasstock(buy), can be from cooldown or it already has stock
hasStock = Math.max(hasStock2, cooled2 - prices[i]);
// from has stock and money
sold = hasStock2 + prices[i];
// from cooldown, or sold
cooled = Math.max(cooled2, sold2);
}
return Math.max(sold, cooled);
}
}
/**
T: O(n)
S: O(n)
buy sell cooldown buy sell
has stock - 0
sold - 1
cooled - 2
has stock: Math.max(dp[i][0] = dp[i-1][0], dp[i-1][2] - price[i]) -> max(has stock, cooled - price[i])
sold: dp[i][1] = dp[i-1][0] + price[i]
cooled : dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]) -> max(cooled, sold)
return Math.max(sold, cooled); (has stock must not the best result, it has stock)
*/
```
```java
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][3];
dp[0][0] = -prices[0]; // has stock
dp[0][1] = 0; // sold
dp[0][2] = 0; // cooled
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]);
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]);
}
return Math.max(dp[n-1][1], dp[n-1][2]);
}
}
```
1. what part I stuck?
on dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]); //buy
I think about the situation of dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // sell
because sell in i-1 day, can I buy use i - 2 day?
Totally ok! becasue the most optimized case are all dependent, remember?
so I can define i-2 for buying!
2. After seeing solution, think about how this person came out this solution? whatโs their thought process, why we have the same question and same knowledge, but I cant?
3. note strategy! remember it!
time: O(n)
space: O(n)
้้กๆฒๆ้ๅถไบคๆๆฌกๆธ, ๆไปฅ่ท II ้กไผผ, ไฝๆๅทๅปๆ็้ๅถ
After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
ๅ ๆญค๏ผๅฆๆ่ฆๅจ็ฌฌi
ๅคฉ่ฒทๅ
ฅ่ก็ฅจ๏ผ็ฌฌไบๅ็ๆ
่ฝ็งปๆน็จไธญๅฐฑไธ่ฝไฝฟ็จT[i - 1][k][0]
๏ผ่ๆ่ฉฒไฝฟ็จT[i - 2][k][0]
class Solution {
public int maxProfit(int[] prices) {
// on the next day (i.e., cooldown one day).
// dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // sell
// dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]); //buy
if (prices == null || prices.length < 2) return 0;
int n = prices.length;
int dp[][] = new int[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // sell
dp[i][1] = Math.max(dp[i-1][1], (i >= 2 ? dp[i-2][0] : 0) - prices[i]); //buy
}
return dp[n-1][0];
}
}
use variables
time: O(n)
space: O(1)
class Solution {
public int maxProfit(int[] prices) {
// on the next day (i.e., cooldown one day).
// dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // sell
// dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]); //buy
if (prices == null || prices.length < 2) return 0;
int n = prices.length;
int dp0 = 0;
int dp1 = -prices[0];
int prevDp0 = 0;
for (int i = 1; i < n; i++) {
int newDp0 = Math.max(dp0, dp1 + prices[i]); // sell
int newDp1 = Math.max(dp1, prevDp0 - prices[i]); //buy
prevDp0 = dp0;
dp0 = newDp0;
dp1 = newDp1;
}
return dp0;
}
}
Previous188. Best Time to Buy and Sell Stock IVNext714. Best Time to Buy and Sell Stock with Transaction Fee
Last updated