文档章节

188. Best Time to Buy and Sell Stock IV

cofama
 cofama
发布于 2017/05/21 18:13
字数 922
阅读 3
收藏 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];
    }
};

© 著作权归作者所有

共有 人打赏支持
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
Leetcode-Easy 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock 描述: 思路: [1,2,3,4] ==> returns 3 (buy at 1 and sell at 4) [4,3,2,1] ==> returns 0 (don't buy) [4,10,25,2,10] ==> returns 21 (buy at 4 a......

致Great
04/01
0
0
Best Time To Sell Stock 3

题目 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 two transac......

Finley.Hamilton
2014/12/04
0
0
122. Best Time to Buy and Sell Stock II。

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 as many transactions as ......

Leafage_M
01/26
0
0
股票的最大收益(最多交易两次)Best Time to Buy and Sell Stock III

问题: 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 two trans......

叶枫啦啦
2017/12/17
0
0
决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
01/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

FFmpeg Maintainer赵军:FFmpeg关键组件与硬件加速

大家好!我是赵军,现就职于英特尔的DCG从事基于FFmpeg的硬件优化工作,两年多前加入FFmpeg社区,2018年4月成为FFmpeg的其中的一个FFmpeg Maintainer,主要负责FFmpeg的硬件优化工作。 概览:...

yizhichao
23分钟前
0
0
ehlib 修改 使行号字体颜色 与标题字体颜色 一致

对ehlib 显示效果不够满意,而做的调整 修改这个过程:procedure TCustomDBGridEh.DrawIndicatorCell(ACol, ARow: Longint; AreaCol, AreaRow: Longint; ARect: TRect; AState: TGri......

vga
49分钟前
1
0
Bash重定向详解

Bash重定向详解 Bash的重定向指的是将命令的输入和输出导向不同地方,而不是默认的标准输入、标准输出和标准错误。Bash的重定向实际上是对标准输入、标准输出和标准错误的重置,进而将所需输...

小陶小陶
今天
3
0
EventBus原理深度解析

一、问题描述 在工作中,经常会遇见使用异步的方式来发送事件,或者触发另外一个动作:经常用到的框架是MQ(分布式方式通知)。如果是同一个jvm里面通知的话,就可以使用EventBus。由于Event...

yangjianzhou
今天
29
0
OpenCV图像处理实例:libuv+cvui显示摄像头视频

#include <iostream>#include <opencv2/opencv.hpp>#define CVUI_IMPLEMENTATION#include <cvui.h>extern "C"{#include <uv.h>}using namespace std;#define WINDOW_NAM......

IOTService
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部