题解 | #买卖股票的最好时机(三)#

import java.util.*;


public class Solution {

    //最多进行两次买入卖出，
    //此时股票的状态相对于第二题多了几种
    //dp[i][0]表示到第i天为止没有买过股票的最大收益
    //1买过1次未卖成
    //2买过一次卖出一次
    //3买个两次卖出1次
    //4买过2次卖出2次
   
    public int maxProfit (int[] prices) {
       int n = prices.length;
        int[][] dp = new int[n][5];
        //初始化dp为最小
        Arrays.fill(dp[0], -10000);
        //第0天不持有状态
        dp[0][0] = 0;
        //第0天持有股票
        dp[0][1] = -prices[0];
        //状态转移
        for(int i = 1; i < n; i++){
             //未买过
            dp[i][0] = dp[i - 1][0];
            //买1，未买出分为之前买过一次和当天买
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//          买卖1次，分为之前买卖完成，和今天卖出
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            //买入2卖出1，分为当天买入第二个和之前买入第二个
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            //卖出2次，分为之前完成和当天卖出第二个
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        //选取最大值（一定在都卖出的情况下），可以只操作一次
        return Math.max(dp[n - 1][2],Math.max(0, dp[n - 1][4]));
    }
}