123. 买卖股票的最佳时机 III - Java 动态规划

原题地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

题解

设dp[i][j]为在第i天进行了j操作后的最大利润，其中

j=0为第一次买入
j=1为第一次卖出
j=2为第二次买入
j=3为第二次卖出

对于第一次买入，我们在此之前由于未进行任何操作，利润必然是负的，即

对于第一次卖出，我们只需要找到第一次买入时的利润最大值（dp[j][0]都为负数，越大的值代表买入的成本越少），加上卖出的利润即可，即

$，其中$

对于第二次买入，我们只需要找到第一次卖出时的利润最大值，减去买入的成本，即

$，其中$

对于第二次卖出，我们只需要找到第二次买入时的利润最大值，加上卖出的利润即可，即

$，其中$

由于存在prices中只支持一次买入卖出的操作的可能性，答案需要在第一次卖出和第二次卖出的所有值中寻找最大值

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==1)return 0;
        int[][] dp=new int[prices.length][4];
        int max1in=Integer.MIN_VALUE,max2in=Integer.MIN_VALUE;
        int max1out=Integer.MIN_VALUE,max2out=Integer.MIN_VALUE;
        //0第一次买入 1第一次卖出 2第二次买入 3第二次卖出
        for (int i=0;i<prices.length;i++){
            dp[i][0]=0-prices[i];
            max1in=Math.max(max1in,dp[i][0]);
            if(i>0){
                dp[i][1]=max1in+prices[i];
                max1out=Math.max(max1out,dp[i][1]);
            }
            if(i>1){
                dp[i][2]=max1out-prices[i];
                max2in=Math.max(max2in,dp[i][2]);
            }
            if(i>2){
                dp[i][3]=max2in+prices[i];
                max2out=Math.max(max2out,dp[i][3]);
            }
        }
        return Math.max(max2out,max1out);
    }
}