NC135. 股票交易的最大收益（二）

描述

假定你知道某只股票每一天价格的变动。 你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。 请设计一个函数，计算你所能获得的最大收益。

1. 动态规划

跟NC134的分析思路一样，第n天的最大收益只与前面一天的最大收益有关，而与每一天的具体操作无关，因此本题适用于动态规划。

本题可以用一个状态机描述，分别是没交易，第1/2次交易有股票，第1/2次交易无股票。因此适用于状态机转移型dp。

用1~5分别表示空仓，第1次交易有股票，第1次交易无股票，第2次交易有股票，第2次交易无股票，根据状态机转移图，每个节点都可能由它的入边转移过来。那么令$dp[i][s]dp[i][s]$表示前i天，最后一天的状态为s时的最大收益。那么有：

• 状态1： 没有入边，也没有利润，即dp[i][1]=0
• 状态2：由状态2和状态1买股票转移来, dp[i][2] = max(dp[i-1][2], dp[i-1][1]-p[i])
• 状态3：由状态2和状态3卖股票转移来，即dp[i][3] = max(dp[i-1][3], dp[i-1][2]+p[i])
• 状态4：同上，dp[i][4] = max(dp[i-1][4], dp[i-1][3]-p[i])
• 状态5：同上，dp[i][5] = max(dp[i-1][5], dp[i-1][4]+p[i])

最终能获取最大利润的时候，一定不能有股票，因此答案是max(dp[n][1], dp[n][3], dp[n][5]).

class Solution {
public:
    int dp[200010][6];
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0) return 0;
        // 因为求最大值，所以默认值为负无穷
        memset(dp, -0x3f, sizeof(dp));
        
        dp[0][1]=0, dp[0][2]=-prices[0]; // 初始状态，第0天可以空仓，可以买股票
        
        for(int i=1;i<len;i++){
            // 枚举每个状态的转移
            dp[i][1]=0;
            dp[i][2]=max(dp[i-1][1]-prices[i],dp[i-1][2]);
            dp[i][3]=max(dp[i-1][2]+prices[i],dp[i-1][3]);
            dp[i][4]=max(dp[i-1][3]-prices[i],dp[i-1][4]);
            dp[i][5]=max(dp[i-1][4]+prices[i],dp[i-1][5]);
        }
        return max(max(dp[len-1][3],dp[len-1][5]),0);
    }
};

• 时间复杂度：$O(n)O(n)$, 遍历了一次数组。
• 空间复杂度：$O(n)O(n)$, dp数组长度为n的常数倍。

2. 空间优化的动态规划

我们发现dp[i]只和dp[i-1]有关系，所以可以压缩1维。思路基本同上

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& p) {
        int n = p.size();
        if (n == 0) return 0;
        
        int b1,b2,s1,s2; // 分别维护第一次、第二次交易买卖的最大利润
        b1 = b2 = -p[0], s1 = s2 = 0;
        
        for (auto i : p) {
            b1 = max(b1, -i);
            b2 = max(b2, s1-i);
            s1 = max(s1, b1+i);
            s2 = max(s2, b2+i);
        }
        
        return max({s1, s2, 0});
    }
};

• 时间复杂度：$O(n)O(n)$, 遍历了一次数组。
• 空间复杂度：$O(1)O(1)$, 常数个变量。