Leetcode 188 Best Time to Buy and Sell Stock IV

triplebee

发布于 2018-01-12 14:46:14

6220

发布于 2018-01-12 14:46:14

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

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).

买股票问题升级版，可以购买k次。

利用买股票问题的第三个变式，可以构造两个dp数组。

sell[i]表示第i次卖出后最大持有的金钱

buy[i]表示第i次买入后最大持有的金钱

卖出的钱由买入的钱加上当前股票卖出的钱，买入的钱由前一次卖出的钱减去当前买股票花去的，因此可以得到两个转移方程

sell[j] = max(sell[j], buy[j] + prices[i]);
buy[j] = max(buy[j], sell[j-1] - prices[i]);

有个小陷阱，k可能很大，达到比总天数多，这种情况下，问题等价于买卖任意次，直接贪心就可以了

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(k > prices.size())
        {
            int res = 0;
            for(int i = 1 ; i < prices.size(); i++) if(prices[i] > prices[i-1]) res += prices[i]-prices[i-1];
            return res;
        }
        vector<int> sell(k+1, 0), buy(k+1, INT_MIN);
        for(int i = 0; i < prices.size() ; i++)
        {
            for(int  j = k; j > 0 ; j--)
            {
                sell[j] = max(sell[j], buy[j] + prices[i]);
                buy[j] = max(buy[j], sell[j-1] - prices[i]);
            }
        }
        return sell[k];
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-03-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm