题目描述

sell之后的一天必须是cooldown

样例

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

算法1

DP $O(n)$

f[i]: 第i天结束时，不持有股票的最大获利
g[i]: 第i天结束时，持有股票的最大获利

f[i] = max( 第i天什么都不做: f[i-1]; 或者第i天卖出股票: x[i] + g[i-1] )
g[i] = max( 第i天什么都不做: g[i-1];
或者第i天买入股票, 当第i天是buy，而题目要求sell的下一天要cooldown，所以i-1不能是sell；
也不可能是buy，因为不能连续buy；
所以第i-1天只能是cooldown, max(f[i-2], g[i-2])，
而 f[i-2] > g[i-2]，所以综上，是 f[i-2] - x[i]
)

综上
for i=0..n-1:
f[i] = max( f[i-1], x[i] + g[i-1] )
g[i] = max( g[i-1], -x[i] + f[i-2] )

f[0]=0, g[0] = -x[i]; f[1]= max(f[0], x[1]-x[0]), g[1]=max(-x[0], -x[1])
res = f[n-1]

C++ 代码

    int maxProfit(vector<int>& x) {
        int n = x.size();
        if(n<=1) return 0;

        vector<int> f(n, 0), g(n, 0);
        f[0] = 0; g[0] = -x[0];
        f[1] = max(0, x[1]-x[0]);
        g[1] = max(-x[0], -x[1]);

        for(int i=2; i<n; i++) {
            f[i] = max( f[i-1], x[i]+g[i-1]);
            g[i] = max( g[i-1], -x[i]+f[i-2]);
        }

        return f[n-1];
    }

算法2

DP $O(n)$

解法1：参考

f[i]: max profit ending at day i.
在day i，有4种选择，buy, sell, cooldown, 或者什么都不干。什么都不干和cooldown是一样的。
1. 最后一天不可能是buy，因为没有机会卖出了。
2. cooldown或啥都不干，f[i] = f[i-1]
3. sell，此时考虑卖的的stock是在day j买入的，j=0..i-1
f[i] = max { p[i]-p[j] + profit of day j-1 }

What is the profit of day j-1? 考虑day j-1:
1. j-1不能是buy，因为day j是buy，不能连续buy
2. j-1不能是sell，因为否则day j要cooldown
所以day j—1只能是cooldown，profit与f[j-2]相同。

这样，f[i] = max { p[i]-p[j] + f[j-2] | for j=0..i-1 }
time O(n^2), space O(n)

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n<=1) return 0;

        int f[n]={0};
        int res = 0;
        for(int i=1; i<n; i++) {
            f[i] = f[i-1];
            for(int j=0; j<i; j++) {
                int prev_profit = (j>=2? f[j-2] : 0);
                f[i] = max(f[i], prices[i] - prices[j] + prev_profit);
            }       
            res = max(res, f[i]);
        }
        return res;
    }

优化时间：

for(i=...) {
    for(j=...) {
        f[i] = max { p[i] - p[j] + f[j-2]}
    }
}
--> 用maxdiff记录moving max diff。
maxdiff = -prices[0];
for(i=1..n-1) {
    f[i] = f[i-1];
    f[i] = max(f[i], p[i] + maxdiff);
    maxdiff = max(maxdiff, (i>=2? f[i-2] :0) - p[i] );
    ...
}

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n<=1) return 0;

        int f[n]={0};
        int res = 0;

        int maxdiff = -prices[0]; // f[j-2] - prices[j]
        for(int i=1; i<n; i++) {
            f[i] = f[i-1];
            f[i] = max(f[i], prices[i] + maxdiff );

            maxdiff = max( maxdiff, ( i>=2 ? f[i-2] : 0) - prices[i] ); 

            res = max(res, f[i]);
        }

        return res;
    }