[leetcode] Best Time to Buy and Sell Stock IV 1


Best Time to Buy and Sell Stock IV

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.

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

Untitled

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

 

 


Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

One thought on “[leetcode] Best Time to Buy and Sell Stock IV