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

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

思路：
自己没有想出来解法，参见了其他人的解法。
动态规划，局部最优与全局最优。
我们需要维护如下两个量：
global[i][j]:当前到达第i天最多可以进行j次交易，所得到的最大利润。
local[i][j]:当前到达第i天最多可以进行j次交易，而且最后一次交易在当天卖出，所得到的最大利润。
状态转移方程：
global[i][j] = max(local[i][j], global[i-1][j])
上述方程比较两个量的大小：①当前局部最大值；②过往全局最大值。
local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)
上述方程比较两个量的大小：
①全局到i-1天进行j-1次交易，然后加上今天的交易（如果今天的交易赚钱的话）。
②取局部第i-1天进行j次交易，然后加上今天的差值（local[i-1][j]是第i-1天卖出的交易，它加上diff后变成第i天卖出，并不会增加交易次数。无论diff是正还是负都要加上，否则就不满足local[i][j]必须在最后一天卖出的条件了）
另外需要注意的一个问题是，当k远大于数组的大小时，上述算法将变得低效。因此将其改用不限交易次数的方式解决。

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];
}