188. Best Time to Buy and Sell Stock IV
博客专区 > cofama 的博客 > 博客详情
188. Best Time to Buy and Sell Stock IV
cofama 发表于12个月前
188. Best Time to Buy and Sell Stock IV
  • 发表于 12个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

原题链接

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

这题很明显需要用一个二维数组,dp[i][j]表示到第i天为止(i、j都从0开始),最多进行j次交易时获得的最大利润。由于一次交易最少要两天(一买一卖),所以首先考虑一种特殊情况k*2>=prices.size(),也就是说可以进行任意次交易,反正也不可能超过k次。这时,如果今天价格大于昨天的价格,在今天卖出一定可以增加利润,增加额为今天和昨天的价格差。这个增加有两种途径:第一种,昨天买进,今天卖出;第二种,昨天之前买进,原计划在昨天卖出,但我现在更改计划,今天才卖出。分析一下prices数组,假设今天是第i天,上一次卖出是第j天,很明显prices[j,...,i-1]是递减数列,也就是说昨天(i-1)的价格是第j天之后最小的,所以昨天买进能获得最大利润,这是第一种途径。当j=i-1时,就变成了第二种途径。再考虑一种情况,如果改变计划第j天不卖了,改为今天才卖出,那么利润增额为prices[i]-prices[j],但由于prices[j]>prices[i-1],所以prices[i]-prices[j]<prices[i]-prices[i-1],也就是说这种操作没有昨天买今天卖的利润高。

考虑完特殊情况,剩下的一般情况就要用动态规划解决了。 首先是初始条件:最大交易次数为0,利润必定为0,所以dp[i][0]=0;天数为1,无法进行交易,利润也为0,所以dp[0][j]=0。接下来考虑状态转移方程,分为两种情形:1.今天价格比昨天高,2.今天价格不比昨天高。

第1种情况:不像特殊情形可以进行任意次交易,考虑到交易次数的限制,今天可能卖也可能不卖,要看哪种利润高。不卖的话,显然dp[i][j]=dp[i-1][j]。卖的话,我们不知道最后一次买进是哪一天,假设是第ii天(ii<i),那么dp[i][j]=max(dp[ii-1][j-1]+prices[i]-prices[ii])=max(dp[ii-1][j-1]-prices[ii])+prices[i],j-1是因为今天卖出的这次交易不计算在内。这样,我们就要遍历所有0到i之间的ii找出最大值。为了避免遍历ii,可以在遍历i的时候,跟踪记录dp[i-1][j-1]-prices[i]的最大值。

第2种情况:今天价格不比昨天高,那么价格从上一次卖出到今天是递减数列,今天卖出是不会增加利润的。dp[i][j]=dp[i-1][j],顺便更新dp[i-1][j-1]-prices[i]的最大值。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        if(prices.size()<=k*2) {
            int profit=0;
            for(int i=1; i<prices.size(); i++) {
                if(prices[i]>prices[i-1]) {
                    profit += prices[i]-prices[i-1];
                }
            }
            return profit;
        }
        
        int dp[prices.size()][k+1];
        int lastbuy, p1, p2;
        for(int i=0; i<prices.size(); i++)
            dp[i][0]=0;
        for(int j=1; j<=k; j++)
            dp[0][j]=0;
        
        for(int j=1; j<=k; j++) {
            lastbuy=0-prices[0];
            for(int i=1; i<prices.size(); i++) {
                if(prices[i]>prices[i-1]) {
                    dp[i][j] = max(prices[i]+lastbuy, dp[i-1][j]);
                }
                else {
                    dp[i][j] = dp[i-1][j];
                    if(dp[i-1][j-1]-prices[i]>lastbuy) lastbuy=dp[i-1][j-1]-prices[i];
                }
            }
        }
        
        return dp[prices.size()-1][k];
    }
};
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 22
码字总数 19162
×
cofama
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: