Massive Algorithms: LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown

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 i^th 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

这题比Best Time to Buy and Sell Stock II多了一个cooldown的条件，就变得麻烦多了。这题是一个多阶段优化问题，首先范围缩小到广搜，贪心或者动规。因为每步之间互相牵连，贪心显然不行。广搜固然可以，不过是O(2^n)复杂度，所以我们先考虑用动规。

对于每一天，有三种动作，buy, sell, cooldown, sell 和 cooldown 可以合并成一种状态，因为手里最终没有股票。最终需要的结果是 sell，即手里股票卖了获得最大利润。我们可以用两个数组来记录当前持股和未持股的状态，令sell[i] 表示第i天未持股时，获得的最大利润，buy[i]表示第i天持有股票时，获得的最大利润。

对于sell[i]，最大利润有两种可能，一是今天没动作跟昨天未持股状态一样，二是今天卖了股票，所以状态转移方程如下：

sell[i] = max{sell[i - 1], buy[i-1] + prices[i]}

对于buy[i]，最大利润有两种可能，一是今天没动作跟昨天持股状态一样，二是前天卖了股票，今天买了股票，因为 cooldown 只能隔天交易，所以今天买股票要追溯到前天的状态。状态转移方程如下：

buy[i] = max{buy[i-1], sell[i-2] - prices[i]}

最终我们要求的结果是sell[n - 1]，表示最后一天结束时，手里没有股票时的最大利润。

这个算法的空间复杂度是O(n)，不过由于sell[i]仅仅依赖前一项，buy[i]仅仅依赖前两项，所以可以优化到O(1)，具体见第二种代码实现

    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;   // sell[i]
        int prevSell = 0;  // sell[i-2]
        int buy = -prices[0]; // buy[i]

        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

LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown

Labels

Popular Posts