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

思路在代码中有详细的解释：状态的构建是最重的一步，（部分引用自：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/tong-su-yi-dong-de-dong-tai-gui-hua-jie-fa-by-marc/)

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if(prices==null||prices.length==0){
            return 0;
        }
        int n=prices.length;
        //具体一天结束时的6种状态：
    // 未持股，未卖出过股票：说明从未进行过买卖，利润为0
    // dp[i][0][0]=0
    // 未持股，卖出过1次股票：可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）
    // dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])
    // 未持股，卖出过2次股票:可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）
    // dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])
    // 持股，未卖出过股票：可能是今天买的，也可能是之前买的（昨天也持股）
    // dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])
    // 持股，卖出过1次股票：可能是今天买的，也可能是之前买的（昨天也持股）
    // dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])
    // 持股，卖出过2次股票：最多交易2次，这种情况不存在,不需要处理
    // dp[i][1][2]=float('-inf')
//     后续还可以进行空间优化，但要注意是倒序进行
        int[][][] dp=new int[n+1][2][3];
        dp[0][1][0]=Integer.MIN_VALUE;
        dp[0][1][1]=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++){
            dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][0][0]-prices[i-1]);
            dp[i][0][1]=Math.max(dp[i-1][0][1],dp[i-1][1][0]+prices[i-1]);
            dp[i][1][1]=Math.max(dp[i-1][1][1],dp[i-1][0][1]-prices[i-1]);
            dp[i][0][2]=Math.max(dp[i-1][0][2],dp[i-1][1][1]+prices[i-1]);
        }
        
        return dp[n][0][2];
        
    }
}