LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

Posted on Edited on In Views: Valine:

Code

Solution of problem 309 is showed below. You can also find it here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() < 2) return 0;
        //s0 denote maxprofit at i-th day without stock
        //s1 denote maxprofit at i-th day with stock
        //s2 denote maxprofit at i-th day when cooling down.
        //s0 could be transited from s0 at i-1th day (do nothing), or from s1 at i-1th day (sell)
        //s1 could be transited from s1 at i-1th day (do nothing), or from s2 at i-1th day (cool to buy)
        //s2 could be transited from s2 at i-1th day (do nothing), or from s0 at i-1th day (do nothing)
        int s0 = 0, s1 = -1e9, s2 = 0;
        for(const auto &p: prices) {
            int tmp = s0;
            s0 = max(s0, s1 + p);
            s1 = max(s1, s2 - p);
            s2 = max(s2, tmp);
        }
        return max(s0, s2);
    }
};

Solution

The method of the solution is from Discuss.

There is another method which use operations rather than states to record status and do calculation.

Valueable Function

The interest part of the first solution is that it uses state machine and minimizes the memory usage by just storing constant level variables. However, it can only be applied in the situation. If the problem said you can only buy stock two days later after selling it, the solution cannot hold it. So the second solution is versatility.