Best Time to Buy and Sell Stock IV

Say you have an array for which the i^th 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.

tag: dynamic programming

很棒的题。利用全局最优解和局部最优解来解。二维的动态规划问题

我们维护两个二维数组local[size][k],和global[size][k]

global[i][j]表示到第i天时，完成j次交易所能达成的最大利润。

local[i][j]表示到第i天时，完成j次交易，且第j次交易在第i天卖出所能达成的最大利润。

这是二维动态规划问题，因为我们需要利用k-1次交易的信息推出k次交易的最大利润；又要用i-1天的交易信息推测出i天的最大利润。

我们引入local变量是为了实现在时间上的递推；

我们在内层的for循环是为了时间在交易次数上的递推。

我们记int diff = prices[i] – prices[i – 1]

对于global的状态转移方程：

global[i][j] = max(global[i-1][j], local[i][j])

意思是，i天完成j次交易的最大利润为i-1天完成j次交易的利润和i天完成j次交易且最后一次交易在最后一天卖出的利润两者的最大值。（有点绕）

对于local的状态转移方程：

local[i][j] = max(global[i – 1][j – 1] + max(diff, 0), local[i-1][j] + diff)

意思是，

global[i – 1][j – 1] + max(diff, 0)：i-1天完成j-1次交易，第j次交易在第i天当天买卖（0）或者第i-1天买，第i天卖（diff）的最大值。

local[i-1][j] + diff：i-1天完成j次交易且第j次交易在i-1天卖出，再在第i-1天买入，在第i天卖出的最大值。（这样第j次交易连起来了，还是j次交易）

当k大于prices.size()时，问题退化成 Best Time to Buy and Sell Stock II。不需要用n*k的时间求解。

另外，这里做了一个优化，不需要真的开两个二维数组出来，而是用两个一维数组在循环中不断交替迭代。因为在第i次循环时，我们只需要第i-1次的信息。

内层循环我们从j=k遍历至1，因为local的状态转移方程中存在这一项global[i – 1][j – 1]，我们必须在更改j-1之前把j更新掉，所以需要从大到小访问k。

class Solution {
public:
//local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
//global[i][j] = max(global[i - 1][j], local[i][j])
    int maxProfit(int k, vector<int> &prices){
        size_t size = prices.size();
        if(k >= size){
            return maxProfit(prices);    
        }
        int global[k+1] = {0};
        int local[k+1] = {0};
        for(int i = 1; i < size; i++){
            int diff = prices[i] - prices[i - 1];
            for(int j = k; j >= 1; j--){
                local[j] = max(global[j - 1] + max(diff, 0), local[j] + diff);
                global[j] = max(global[j], local[j]);
            }
        }
        return global[k];
    }
    int maxProfit(vector<int> &prices){
        int profit = 0;
        for(int i = 1; i < prices.size(); i++){
            int diff = prices[i] - prices[i - 1];
            profit += max(0, diff);
        }
        return profit;
    }
};

参考资料：http://blog.csdn.net/linhuanmars/article/details/23236995