188. Best Time to Buy and Sell Stock IV

这道题是股票系列的第四题，在第三题的基础上变成了我们最多可以进行N次交易，本题的解法也适用于第三题，只需要将N设置为2就行了嘛。

首先，我们要确定的是，买和卖才算一次交易，而单独的买或者单独的卖不算一次交易。基于这个假定，如果k大于时间长度的一半的话，我们只需要简单的遍历数组，将第二天价格比前一天大的价格的差值累积求和就可以啦。

如果不是这样的话，我们在N天中进行K次交易有多种选择的话，我们可以维护两个数组，分别叫做global和local,我们用二维的数组来进行介绍，但是实际实现时可以使用一维的数组，因为我们是按天迭代的，类似这种情况的我们都可以将二维数组压缩成一维数组来减小空间复杂度。我们首先介绍一下两个数组的含义。
global[i][j]的含义是：在第I天最多进行j次交易，那么所能得到的最大的利润是什么。
local[i][j]的含义是：在第I天最多进行j次交易，并且最后一次交易是发生在第i天时所能得到的最好的利润。

根据这两个数组的含义，我们来讲解一下二者的递推公式，首先我们定义prices[i]-prices[i-1]即两天股票的差值为diff。那么对于global来说，global[i][j] = max(global[i-1][j],local[I][j])，即在最多进行j笔交易的情况下，最后一笔交易是否发生在今天，如果发生在今天所能获得的利润大的话，那么global[i][j] = local[i][j]，如果不是的话，则global[i][j]=global[i-1][j]。对于local来说，local[i][j] = max(local[i-1][j] + diff, global[i-1][j-1]+diff)。也就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local[i-1][j]包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local[i][j]必须在最后一天卖出的条件了）。

好了，明确了上面的递推关系，我们可以写出如下的代码：

class Solution {

    public int maxProfit(int k, int[] prices) {

        if(prices==null || prices.length==0 || k<=0)

            return 0;

        int res = 0;

        if(k>=prices.length / 2){

            for(int i=0;i<prices.length-1;i++)

                if(prices[i+1] > prices[I])

                    res += (prices[i+1] - prices[I]);

        }

        else{

            int[] global = new int[k+1];

            int[] local = 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(local[j] + diff,global[j-1] + diff);

                    global[j] = Math.max(local[j],global[j]);

                }

            }

            res = global[k];

        }

        return res;

    }

}