力扣 123. 买卖股票的最佳时机 III

题目描述：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解析：

动态规划

Java:

public int maxProfit(int[] prices) {
        if(prices.length == 0) {
            return 0;
        }
        int dp[][] = new int[3][prices.length];
        for(int i = 1; i < 3; i++) {
            int maxProfit = -prices[0];
            for(int j = 1; j < prices.length; j++) {
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxProfit);
                maxProfit = Math.max(maxProfit, dp[i-1][j] - prices[j]);
            }
        }
        return dp[2][prices.length-1];
    }

JavaScript:

var maxProfit = function(prices) {
    if(prices.length === 0) {
        return 0;
    }
    const dp = Array.from(Array(3), () => new Array(prices.length));
    for(let i = 0; i < prices.length; i++) {
        dp[0][i] = 0;
    }
    for(let i = 0; i < 3; i++) {
        dp[i][0] = 0;
    }
    for(let i = 1; i < 3; i++) {
        let maxProfit = -prices[0];
        for(let j = 1; j < prices.length; j++) {
            dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxProfit);
            maxProfit = Math.max(maxProfit, dp[i-1][j] - prices[j]);
        }
    }
    return dp[2][prices.length-1];
};