状态机

$ 时间复杂度O(N)，空间O(1)$

每一个状态只用到了上一层的状态，所以可以优化成常数空间

参考文献

算法提高课

二维数组空间代码

class Solution {
public:
    int maxProfit(vector<int>& w) {
        int n = w.size();
        int f[n + 1][3];
        memset(f, -0x3f, sizeof f);
        f[0][1] = 0;
        for (int i = 1 ; i <= n ; i ++){
            int t = w[i - 1];
            f[i][0] = max(f[i][0], f[i - 1][2] + t);
            f[i][1] = max(f[i - 1][0], f[i - 1][1]);
            f[i][2] = max(f[i - 1][1] - t, f[i - 1][2]);
        }
        return max(f[n][0], f[n][1]);
    }
};

常数空间代码

class Solution {
public:

    int maxProfit(vector<int>& w) {
        int n = w.size();
        int a , b, c;
        a = c = -0x3f3f3f3f;
        b = 0;
        for (int i = 1 ; i <= n ; i ++){
            int t = w[i - 1];
            int ta = a,tb = b, tc = c;
            a = max(ta, tc + t);
            b = max(ta, tb);
            c = max(tb - t, tc);
        }
        return max(a, b);
    }
};