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).
Credits:Special thanks to @Freezen for adding this problem and creating all test cases.
Subscribe to see which companies asked this question.

假設(shè)你有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。
設(shè)計(jì)一個(gè)算法來找到最大的利潤(rùn)。你最多可以完成 k 筆交易。
樣例
給定價(jià)格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.

solution

典型的動(dòng)態(tài)規(guī)劃，并且利用局部和全局最優(yōu)，這種思想值得仔細(xì)體會(huì)，好好掌握。
這種局部最優(yōu)與全局最優(yōu)問題
global[i][j] = max(local[i][j], global[i - 1][j])
很容易知道上面這個(gè)遞推式。
關(guān)鍵在于求取局部最優(yōu)的遞推式，在本題中
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
這里我們需要兩個(gè)遞推公式來分別更新兩個(gè)變量local和global
我們定義local[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤(rùn)，此為局部最優(yōu)。然后我們定義global[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易的最大利潤(rùn)，此為全局最優(yōu)
局部最優(yōu)解的遞推式可以這樣理解：

• 在i-1天時(shí)，正在進(jìn)行第j次交易，所以我們最后一天必須將股票賣出，而且這是算在第j次交易當(dāng)中的，這種情況下，local[i - 1][j] + diff，只需將i-1天的局部最優(yōu)解加上最后一天賣出的差值即可，相當(dāng)于將最后一次交易多延遲了一天
• 第二種情況，就是在第i-1天進(jìn)行j-1次交易的全局最優(yōu)解，我們?cè)谧詈笠惶爝€得進(jìn)行一次交易，必須賣出，如果diff大于0，那么就在第i-1天買進(jìn)，i天賣出，如果小于0，就直接在第i天買進(jìn)又賣出，只是為了滿足j次交易，就相當(dāng)于沒有交易，即加上0就可以了。
  這道題還有一個(gè)陷阱，可以優(yōu)化的地方，就是如果k>=prices.length/2。那我們可以理解可以進(jìn)行任意次交易了，因?yàn)橛行Ы灰锥夹枰獌商靵硗瓿?，所以直接使用貪心法就可以算出來了?/li>

public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if(k <=0 || len < 2)
            return 0;
        int maxProfit = 0;
        
        if(k >= len/2) {
            //直接當(dāng)作貪心處理，也就是問題2的答案
            for(int i=1;i<len;i++) {
                int diff = prices[i]-prices[i-1];
                if(diff > 0)
                    maxProfit += diff;
            }
            return maxProfit;
        }
        
        int[][] local = new int[len][k+1];
        int[][] global = new int[len][k+1];
        
        for(int i=1;i<len;i++) {
            int diff = prices[i] - prices[i-1];
            for(int j=1;j<=k;j++) {
                local[i][j] = Math.max(global[i-1][j-1] + Math.max(diff, 0), 
                        local[i-1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i-1][j]);
            }
        }
        return global[len-1][k];
    }