解题思路

Java代码如下：

class Solution {
    int inf = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        /* 
         *  dp[i][j][k]：i表示天数，j表示当前是否持股（j=0、1），k表示卖出的次数（k=0、1、2） 
         */
        int n = prices.length;
        int[][][] dp = new int[n][2][3];
        // 第一天没有操作
        dp[0][0][0] = 0;
        // 第一天不能直接卖出 
        dp[0][0][1] = -inf;
        dp[0][0][2] = -inf;
        dp[0][1][0] = -prices[0];
        // 第一天不能直接卖出
        dp[0][1][1] = -inf;
        dp[0][1][2] = -inf;

        for (int i = 1; i < n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = Math.max(dp[i-1][1][0] + prices[i], dp[i-1][0][1]);
            dp[i][0][2] = Math.max(dp[i-1][1][1] + prices[i], dp[i-1][0][2]);
            // 第i天买入，第i天之前就买入了
            dp[i][1][0] = Math.max(dp[i-1][0][0] - prices[i], dp[i-1][1][0]);
            dp[i][1][1] = Math.max(dp[i-1][0][1] - prices[i], dp[i-1][1][1]);
            dp[i][1][2] = -inf;
        }

        return Math.max(Math.max(dp[n-1][0][1], dp[n-1][0][2]), 0);
    }
}