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 k transactions.

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

思路：
自己沒有想出來解法刽宪，參見了其他人的解法雕凹。
動態(tài)規(guī)劃啥箭，局部最優(yōu)與全局最優(yōu)。
我們需要維護(hù)如下兩個量：
global[i][j]:當(dāng)前到達(dá)第i天最多可以進(jìn)行j次交易扰路，所得到的最大利潤。
local[i][j]:當(dāng)前到達(dá)第i天最多可以進(jìn)行j次交易舅桩，而且最后一次交易在當(dāng)天賣出靶草，所得到的最大利潤。
狀態(tài)轉(zhuǎn)移方程：
global[i][j] = max(local[i][j], global[i-1][j])
上述方程比較兩個量的大心豢选：①當(dāng)前局部最大值丢氢；②過往全局最大值。
local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)
上述方程比較兩個量的大邢雀摹：
①全局到i-1天進(jìn)行j-1次交易疚察，然后加上今天的交易（如果今天的交易賺錢的話）。
②取局部第i-1天進(jìn)行j次交易仇奶，然后加上今天的差值（local[i-1][j]是第i-1天賣出的交易貌嫡，它加上diff后變成第i天賣出，并不會增加交易次數(shù)该溯。無論diff是正還是負(fù)都要加上岛抄，否則就不滿足local[i][j]必須在最后一天賣出的條件了）
另外需要注意的一個問題是，當(dāng)k遠(yuǎn)大于數(shù)組的大小時朗伶，上述算法將變得低效弦撩。因此將其改用不限交易次數(shù)的方式解決步咪。

public int maxProfit(int k, int[] prices) {
    int res = 0;
    if (k < 1 || prices == null || prices.length < 2) {
        return res;
    }
    if (k >= prices.length / 2) return quickSolve(prices);
    
    int[] local = new int[k + 1];
    int[] global = new int[k + 1];
    for (int i = 0; i < prices.length - 1; i++)
    {
        int diff = prices[i+1]-prices[i];
        for(int j = k; j >= 1; j--)
        {
            local[j] = Math.max(global[j-1]+(diff>0?diff:0), local[j]+diff);
            global[j] = Math.max(local[j],global[j]);
        }
    }
    return global[k];
}

private int quickSolve(int[] prices) {
    int len = prices.length, profit = 0;
    for (int i = 1; i < len; i++)
        // as long as there is a price gap, we gain a profit.
        if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
    return profit;
}

下面這種思路更好理解一些：

public int maxProfit1(int k, int[] prices) {
    int n = prices.length;
    if (n <= 1)
        return 0;

    //if k >= n/2, then you can make maximum number of transactions.
    if (k >=  n/2) {
        int maxPro = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1])
                maxPro += prices[i] - prices[i-1];
        }
        return maxPro;
    }

    int[][] dp = new int[k+1][n];
    for (int i = 1; i <= k; i++) {
        int localMax = dp[i-1][0] - prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j-1],  prices[j] + localMax);
            localMax = Math.max(localMax, dp[i-1][j] - prices[j]);
        }
    }
    return dp[k][n-1];
}