leetcode123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][][] dp = new int[2][3][length];
        //第一维表示持有状态，第二维表示交易量（从1开始更符合习惯），第三维表示天数
        dp[0][1][0] = 0;
        dp[1][1][0] = -prices[0];
        dp[0][2][0] = 0;
        dp[1][2][0] = -prices[0];
        for(int i = 1; i < length; i++) {
            dp[0][1][i] = Math.max(dp[0][1][i - 1], dp[1][1][i - 1] + prices[i]);
            //第一次交易不持有股票
            dp[1][1][i] = Math.max(dp[1][1][i - 1], -prices[i]);
            //第一笔交易持有股票
            dp[1][2][i] = Math.max(dp[1][2][i - 1], dp[0][1][i - 1] - prices[i]);
            //第二笔交易持有股票
            dp[0][2][i] = Math.max(dp[0][2][i - 1], dp[1][2][i - 1] + prices[i]);
            //第二笔交易不持有股票
        }
        return dp[0][2][length - 1];
    }
}