Leetcode 123. Best Time to Buy a

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题意：121的followup，现在要求只能进行两次交易，求最大获利。

思路：
自己没有想出解法，参考了discuss的解法。
discuss采用动态规划来解这道题，dp[i][j]代表在第j天交易i次能获得的最大利润。
如果在第j天没有卖出行为，则第j天最大获利与第j-1天最大获利相等，即dp[i][j]等于dp[i][j-1]。
如果在第j天进行卖出，那么最后一次买入在第1天到第j-1天都可能发生，所以dp[i][j]=prices[j] - prices[jj] + dp[i-][jj] { jj in range of [0, j-1] }。
综合以上两种情况：
dp[i][j] = max(dp[i][j-1], prices[j] - prices[jj] + dp[i-1][jj] { jj in range of [0, j-1] })
prices[j]是定值，可以用tmpMax来表示dp[i-1][jj] - prices[jj]{ jj in range of [0, j-1] }.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
        return 0;
    }

    int profit = 0;
    int k = 2;
    int len = prices.length;
    int[][] dp = new int[k][len];
    for (int i = 1; i < k; i++) {
        int tmpMax = dp[i-1][0] - prices[0];
        for (int j = 1; j < len; j++) {
            dp[i][j] = prices[j] + tmpMax;
            tmpMax = Math.max(tmpMax, dp[i-1][j] - prices[j]);
            profit = Math.max(profit, dp[i][j]);
        }
    }

    return profit;
}