LeetCode 121 - Best Time to Buy and Sell Stock
LeetCode - Best Time to Buy and Sell Stock II
LeetCode - Best Time to Buy and Sell Stock III
LeetCode 188 - Best Time to Buy and Sell Stock IV
Leetcode 309 - Best Time to Buy and Sell Stock with Cooldown
LeetCode 714 - Best Time to Buy and Sell Stock with Transaction Fee
leetcode Best Time to Buy and Sell Stock with Cooldown - 细语呢喃
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:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
X. O(N^2) -> O(N)
http://www.programmersought.com/article/3527176644/
This question should be done with dynamic programming.
state definition: dp[i]: the maximum profit that can be obtained on the i-day
state transition equation: dp[i] = max(dp[i-1], dp[j-2] + (prices[i] - prices[j])), 0 < = j < i, which corresponds to the situation of not selling and selling on the i-day.
Write the code very quickly:
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty() || prices.size() == 1)
return 0;
int sz = prices.size();
vector<int> dp(sz, 0);
dp[1] = prices[1] > prices[0] ? prices[1] - prices[0] : 0;
for (int i = 2; i < sz; ++i) {
dp[i] = dp[i-1];
for (int j = 0; j < i; ++j) {
int temp = j-2 < 0 ? prices[i] - prices[j] : dp[j-2] + prices[i] - prices[j];
if (temp > dp[i])
dp[i] = temp;
}
}
return dp.back();
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
Writing code like this can be inefficient.
We observe the state transition equation and turn the latter part into: (dp[j-2] - prices[j]) + prices[i],
For the different i, the front part of (dp[j-2] - prices[j]) is the same, that is, the above code repeatedly calculates this part. The optimized code is:
int maxProfit(vector<int>& prices) {
if (prices.empty() || prices.size() == 1)
return 0;
int sz = prices.size();
vector<int> dp(sz, 0);
dp[1] = prices[1] > prices[0] ? prices[1] - prices[0] : 0;
int tempMax = max(-prices[0], -prices[1]);//tempMax = dp[j-2] - prices[j]
for (int i = 2; i < sz; ++i) {
tempMax = max(tempMax, dp[i-2] - prices[i]);
dp[i] = max(dp[i-1], tempMax + prices[i]);
}
return dp.back();
}
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75928/Share-my-DP-solution-(By-State-Machine-Thinking)
There are three states, according to the action that you can take.
Hence, from there, you can now the profit at a state at time i as:
s0[i] = max(s0[i - 1], s2[i - 1]); // Stay at s0, or rest from s2
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // Stay at s1, or buy from s0
s2[i] = s1[i - 1] + prices[i]; // Only one way from s1
Then, you just find the maximum of s0[n] and s2[n], since they will be the maximum profit we need (No one can buy stock and left with more profit that sell right :) )
Define base case:
s0[0] = 0; // At the start, you don't have any stock if you just rest
s1[0] = -prices[0]; // After buy, you should have -prices[0] profit. Be positive!
s2[0] = INT_MIN; // Lower base case
I think the definitions of buy[i] and sell[i] can be refined to these:
buy[i] : Maximum profit which end with buying on day i or end with buying on a day before i and takes rest until the day i since then.
sell[i] : Maximum profit which end with selling on day i or end with selling on a day before i and takes rest until the day i since then.
int maxProfit(vector<int>& prices){
if (prices.size() <= 1) return 0;
vector<int> s0(prices.size(), 0);
vector<int> s1(prices.size(), 0);
vector<int> s2(prices.size(), 0);
s1[0] = -prices[0];
s0[0] = 0;
s2[0] = INT_MIN;
for (int i = 1; i < prices.size(); i++) {
s0[i] = max(s0[i - 1], s2[i - 1]);
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]);
s2[i] = s1[i - 1] + prices[i];
}
return max(s0[prices.size() - 1], s2[prices.size() - 1]);
}
public int maxProfitFSM(int[] prices) {
if (prices == null || prices.length < 2) return 0;
int[] s0 = new int[2];
int[] s1 = new int[2];
int[] s2 = new int[2];
s0[0] = 0;
s1[0] = -prices[0];
s2[0] = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; ++i) {
s0[i%2] = Math.max(s0[(i-1)%2], s2[(i-1)%2]);
s1[i%2] = Math.max(s1[(i-1)%2], s0[(i-1)%2] - prices[i]);
s2[i%2] = s1[(i-1)%2] + prices[i];
}
return Math.max(s0[(prices.length-1)%2], s2[(prices.length-1)%2]);
}
X. Best
https://blog.csdn.net/Cloudox_/article/details/70785045
这是一个典型的需要动态规划来做的题，有三种操作类型：买入（buy）、卖出（sell）、休息（rest）。根据动态规划的方法，我们需要列出三种操作的计算方程，三个方程分别表示，以这三种操作作为最后一次操作的情况下的最终最大收益。
根据定义，我们来一个个看：
买入的前一天必须是休息，最后一天如果要是买入，那最后还需要消耗一笔金钱，这笔金钱是当日的股票价price，那么方程是：
buy[i] = max{rest[i-1]-price, buy[i-1]}
卖出的前一天必须是买入，最后一天卖出后，会多得到当日的股价price，那么方程是：
sell[i] = max{buy[i-1]+price, sell[i-1]}
休息的话有多种情况，最后一天休息的话，前一天可以是买入、卖出或者休息，且最后一天也不会有进账或者消费，那么方程是：
rest[i] = max{buy[i-1], sell[i-1], rest[i-1]}
但是稍微想一下就知道，最后一天买入后的收益一定小于最后一天休息的收益，由小于最后一天卖出的收益，即：
buy[i] <= rest[i] <= sell[i]
那么我们rest的方程就可以变为：
rest[i] = sell[i-1]
代入buy和sell的方程就是：
buy[i] = max{sell[i-2]-price, buy[i-1]}
sell[i] = max{buy[i-1]+price, sell[i-1]}
由于每次计算第i个值时我们只用到了最多前两个sell和前一个buy，所以我们不需要记录整个数组的buy和sell，将空间复杂度降低到O（1），只需要记录前两个sell和前一个buy，根据代码的写法，我们甚至只需要记录前一个sell，将对sell的计算放在buy之后，那么自然而然就变成前两个sell了
https://leetcode.com/discuss/71391/easiest-java-solution-with-explanations
1. Define States
To represent the decision at index i:
buy[i]: Max profit till index i. The series of transaction is ending with a buy.sell[i]: Max profit till index i. The series of transaction is ending with a sell.
To clarify:
- Till index
i, the buy / sell action must happen and must be the last action. It may not happen at index i. It may happen at i - 1, i - 2, ... 0.
- In the end
n - 1, return sell[n - 1]. Apparently we cannot finally end up with a buy. In that case, we would rather take a rest at n - 1.
- For special case no transaction at all, classify it as
sell[i], so that in the end, we can still return sell[n - 1]. Thanks @alex153 @kennethliaoke @anshu2.
2. Define Recursion
buy[i]: To make a decision whether to buy at i, we either take a rest, by just using the old decision at i - 1, or sell at/before i - 2, then buy at i, We cannot sell at i - 1, then buy at i, because of cooldown.sell[i]: To make a decision whether to sell at i, we either take a rest, by just using the old decision at i - 1, or buy at/before i - 1, then sell at i.
So we get the following formula:
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
3. Optimize to O(1) Space
DP solution only depending on i - 1 and i - 2 can be optimized using O(1) space.
- Let
b2, b1, b0 represent buy[i - 2], buy[i - 1], buy[i]
- Let
s2, s1, s0 represent sell[i - 2], sell[i - 1], sell[i]
Then arrays turn into Fibonacci like recursion:
b0 = Math.max(b1, s2 - prices[i]);
s0 = Math.max(s1, b1 + prices[i]);
4. Write Code in 5 Minutes
First we define the initial states at i = 0:
- We can buy. The max profit at
i = 0 ending with a buy is -prices[0].
- We cannot sell. The max profit at
i = 0 ending with a sell is 0.
public int maxProfit(int[] prices) {
if(prices == null || prices.length <= 1) return 0;
int b0 = -prices[0], b1 = b0;
int s0 = 0, s1 = 0, s2 = 0;
for(int i = 1; i < prices.length; i++) {
b0 = Math.max(b1, s2 - prices[i]);
s0 = Math.max(s1, b1 + prices[i]);
b1 = b0; s2 = s1; s1 = s0;
}
return s0;
}
https://soulmachine.gitbooks.io/algorithm-essentials/java/dp/best-time-to-buy-and-sell-stock-with-cooldown.html
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int[] sell = new int[prices.length];
int[] buy = new int[prices.length];
sell[0] = 0;
buy[0] = -prices[0];
for (int i = 1; i < prices.length; ++i) {
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
buy[i] = Math.max(buy[i - 1], (i > 1 ? sell[i - 2] : 0) - prices[i]);
}
return sell[prices.length - 1];
}
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int curSell = 0;
int prevSell = 0;
int buy = -prices[0];
for (int i = 1; i < prices.length; ++i) {
final int tmp = curSell;
curSell = Math.max(curSell, buy + prices[i]);
buy = Math.max(buy, (i > 1 ? prevSell : 0) - prices[i]);
prevSell = tmp;
}
return curSell;
}
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int n = prices.length;
int[] sell = new int[n];
int[] cooldown = new int[n];
int diff = -prices[0];
for (int i=1; i<n; i++) {
cooldown[i] = Math.max(cooldown[i-1], sell[i-1]);
sell[i] = Math.max(sell[i], diff+prices[i]);
diff = Math.max(diff, cooldown[i-1]-prices[i]);
}
return Math.max(cooldown[n-1], sell[n-1]);
}
http://www.cnblogs.com/grandyang/p/4997417.html
而这道题与上面这些不同之处在于加入了一个冷冻期Cooldown之说，就是如果某天卖了股票，那么第二天不能买股票，有一天的冷冻期
此题需要维护三个一维数组buy, sell，和rest。其中：
buy[i]表示在第i天之前最后一个操作是买，此时的最大收益。
sell[i]表示在第i天之前最后一个操作是卖，此时的最大收益。
rest[i]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。
我们写出递推式为：
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])
上述递推式很好的表示了在买之前有冷冻期，买之前要卖掉之前的股票。一个小技巧是如何保证[buy, rest, buy]的情况不会出现，这是由于buy[i] <= rest[i]， 即rest[i] = max(sell[i-1], rest[i-1])，这保证了[buy, rest, buy]不会出现。
另外，由于冷冻期的存在，我们可以得出rest[i] = sell[i-1]，这样，我们可以将上面三个递推式精简到两个：
buy[i] = max(sell[i-2] - price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
我们还可以做进一步优化，由于i只依赖于i-1和i-2，所以我们可以在O(1)的空间复杂度完成算法
int maxProfit(vector<int>& prices) {
int buy = INT_MIN, pre_buy = 0, sell = 0, pre_sell = 0;
for (int price : prices) {
pre_buy = buy;
buy = max(pre_sell - price, pre_buy);
pre_sell = sell;
sell = max(pre_buy + price, pre_sell);
}
return sell;
}
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75927/Share-my-thinking-process
The key for dp is to find the variables to represent the states and deduce the transition function.
Of course one may come up with a O(1) space solution directly, but I think it is better to be generous when you think and be greedy when you implement.
The natural states for this problem is the 3 possible transactions : buy, sell, rest. Here restmeans no transaction on that day (aka cooldown).
Then the transaction sequences can end with any of these three states.
For each of them we make an array, buy[n], sell[n] and rest[n].
buy[i] means before day i what is the maxProfit for any sequence end with buy.
sell[i] means before day i what is the maxProfit for any sequence end with sell.
rest[i] means before day i what is the maxProfit for any sequence end with rest.
Then we want to deduce the transition functions for buy sell and rest. By definition we have:
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])
Where price is the price of day i. All of these are very straightforward. They simply represents :
(1) We have to `rest` before we `buy` and
(2) we have to `buy` before we `sell`
One tricky point is how do you make sure you sell before you buy, since from the equations it seems that [buy, rest, buy] is entirely possible.
Well, the answer lies within the fact that buy[i] <= rest[i] which means rest[i] = max(sell[i-1], rest[i-1]). That made sure [buy, rest, buy] is never occurred.
A further observation is that and rest[i] <= sell[i] is also true therefore
rest[i] = sell[i-1]
Substitute this in to buy[i] we now have 2 functions instead of 3:
buy[i] = max(sell[i-2]-price, buy[i-1])
sell[i] = max(buy[i-1]+price, sell[i-1])
This is better than 3, but
we can do even better
Since states of day i relies only on i-1 and i-2 we can reduce the O(n) space to O(1). And here we are at our final solution:
public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
for (int price : prices) {
prev_buy = buy;
buy = Math.max(prev_sell - price, prev_buy);
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}
https://leetcode.com/discuss/73617/7-line-java-only-consider-sell-and-cooldown
Define:
profit1[i] = max profit on day i if I sell
profit2[i] = max profit on day i if I do nothing
How will those profits on day i+1 relate to profits on day i ?
1. profit1[i+1] means I must sell on day i+1, and there are 2 cases:
a. If I just sold on day i, then I have to buy again on day i and sell on day i+1
b. If I did nothing on day i, then I have to buy today and sell today
Taking both cases into account, profit1[i+1] = max(profit1[i]+prices[i+1]-prices[i], profit2[i])
2. profit2[i+1] means I do nothing on day i+1, so it will be max(profit1[i], profit2[i])
The problem requires cooldown one day after sell, but why does 'profit1=Math.max(profit1+prices[i]-prices[i-1], profit2);' work? I cann't understand, could you please explain it?
Because if you sell on day i and buy again on day i, it's equivalent to doing nothing on day i.
public int maxProfit(int[] prices) {
int profit1=0, profit2=0;
for(int i=1; i<prices.length; i++){
int copy=profit1;
profit1=Math.max(profit1+prices[i]-prices[i-1], profit2);
profit2=Math.max(copy, profit2);
}
return Math.max(profit1, profit2);
}
https://discuss.leetcode.com/topic/32836/o-n-java-solution-3ms
Basically for day i there are three types of action we can consider: sell, buy and cooldown.
If we want to buy, then i-1 day must be cooldown, so after buy today our portfolio value should be cooldown-prices[i]. if this number is small than buy itself, then we don't buy today.
If we want to cooldown, then i-1 day must be cooldown or sell. So we take the max of these two.
If we want to sell, then before day i, we must have position, so after sell our portfolio value should be day i-1's buy+prices[i]. if this value is smaller than sell itself, then we don't sell today.
if (prices.length<2) return 0;
int buy = -prices[0], sell = 0, cooldown = 0;
for(int i=1; i<prices.length; i++) {
int temp = buy;
buy = Math.max(buy, cooldown-prices[i]);
cooldown = Math.max(sell, cooldown);
sell = Math.max(sell, temp+prices[i]);
}
return sell>cooldown?sell:cooldown;
DP，we can create two array, buy and sell. buy[i] means we buy a stock at day i , and sell[i] means we sell a stock at day i.
so, we have twoequations :
- buy[i] = max(buy[i-1] , sell[i-2] – prices[i]) // So we should use sell[i-2] means we cooldown one day.
- sell[i] = max(sell[i-1], buy[i-1] + prices[i])
finally, return the max(buy[n-1] , sell[n-1])
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices) < 2: return 0
n = len(prices)
buy, sell = [0] * n, [0] * n
buy[0] = -prices[0]
buy[1] = max(-prices[0], -prices[1])
sell[1] = max(0, prices[1] - prices[0])
for i in xrange(2, n):
buy[i] = max(sell[i - 2] - prices[i], buy[i - 1])
sell[i] = max(buy[i - 1] + prices[i], sell[i - 1])
return max(buy[n - 1], sell[n - 1])
http://bookshadow.com/weblog/2015/11/24/leetcode-best-time-to-buy-and-sell-stock-with-cooldown/
引入辅助数组sells和buys
sells[i]表示在第i天卖出股票所能获得的最大累积收益
buys[i]表示在第i天买入股票所能获得的最大累积收益
初始化令sells[0] = 0，buys[0] = -prices[0]
第i天交易时获得的累计收益只与第i-1天与第i-2天有关
记第i天与第i-1天的价格差：delta = price[i] - price[i - 1]
状态转移方程为：
sells[i] = max(buys[i - 1] + prices[i], sells[i - 1] + delta)
buys[i] = max(sells[i - 2] - prices[i], buys[i - 1] - delta)
上述方程的含义为：
第i天卖出的最大累积收益 = max(第i-1天买入~第i天卖出的最大累积收益, 第i-1天卖出后反悔~改为第i天卖出的最大累积收益)
第i天买入的最大累积收益 = max(第i-2天卖出~第i天买入的最大累积收益, 第i-1天买入后反悔~改为第i天买入的最大累积收益)
而实际上：
第i-1天卖出后反悔，改为第i天卖出 等价于 第i-1天持有股票，第i天再卖出
第i-1天买入后反悔，改为第i天买入 等价于 第i-1天没有股票，第i天再买入
所求的最大收益为max(sells)。显然，卖出股票时才可能获得收益
引入辅助数组sells和buys
sells[i]表示在第i天不持有股票所能获得的最大累计收益
buys[i]表示在第i天持有股票所能获得的最大累计收益
初始化数组：
sells[0] = 0
sells[1] = max(0, prices[1] - prices[0])
buys[0] = -prices[0]
buys[1] = max(-prices[0], -prices[1])
状态转移方程：
sells[i] = max(sells[i - 1], buys[i - 1] + prices[i])
buys[i] = max(buys[i - 1], sells[i - 2] - prices[i])
所求最大收益为sells[-1]
X.
https://juejin.im/post/5c6403056fb9a04a0b22ad24
- 状态：colldown 表示当天休息能够获得的最大价值，hold 表示当天持有股票能够获得的最大价值，sold 表示当天持有股票能够获得的最大价值。
- 初始状态：colldown = 0, hold = －∞, sold = 0。
- 状态转移方程：colldown ：如果当前休息，那么当前的价值可以来自于前一天休息或者前一天卖出股票（前一天买进股票不会产生收益），所以 colldown = max(colldown, sold)；hold ：如果当天选择继续持有股票，则当天可以选择继续持有昨天的股票，或者昨天休息今天买进股票，所以hold = max(oldhold, colldown - prices[i]); sold :当天卖出股票，则其价值只能来自于昨天买进今天卖出 sold = oldhold + prices[i]。
import sys
class Solution:
def maxProfit(self, prices: 'List[int]') -> 'int':
if len(prices) < 2: return 0
colldown, hold, sold = 0, -sys.maxsize, 0
for day in range(len(prices)):
oldhold = hold
hold = max(oldhold, colldown - prices[day])
colldown = max(colldown, sold)
sold = oldhold + prices[day]
return max(colldown, sold)
https://leetcode.com/discuss/71259/share-my-3ms-java-dp-solution
https://leetcode.com/discuss/72892/very-easy-to-understand-one-pass-solution-with-no-extra-space
TODO:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/discuss/75924/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems
O(2^n)复杂度，所以我们先考虑用动规。