文档章节

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 121. Best Time to Buy and Sell Stock

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 Version 2 Version 3 Reference https://leetcode.com/problems/best-time-to-buy-and-sell-stock......

SnailTyan
10/19
0
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
Leetcode 122. Best Time to Buy and Sell Stock II

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/83546622 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
10/30
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

没有更多内容

加载失败,请刷新页面

加载更多

get和post详解

get和post是表单提交的两种方式,get请求数据通过域名后缀URL传送,用户可见,不安全,post请求数据通过在请求报文正文里传输,相对比较安全。get是通过URL传递表单值,post通过URL看不到表单...

青衣霓裳
28分钟前
1
0
linux-如何快速替换IP

在Linux在做高可用的时候,经常会使用到虚拟IP。在windows上一个网卡可以配置两个IP,在Linux直接使用ip命令就可以添加了。 添加 ip address add 192.168.1.200/24 broadcast 192.168.1.255 ...

Linux就该这么学
33分钟前
0
0
Unix-Linux 编程实践教程 第五章 小结

设备文件中用逗号连接起来的两个数字为主设备号和从设备号。主设备号确定实际的设备驱动程序,从设备号作为参数。 如下图中的,主设备号-4,从设备号-2 设备文件中的i-node存储的是指向内核子...

Explorer0
35分钟前
1
0
virtual box centos7 挂载进行文件和共享使用说明

一、virtualbox共享文件夹无访问权限问题解决方法 (转载 http://www.cnblogs.com/zhuguanhao/p/6192777.html) 这篇文章主要介绍了virtualbox共享文件夹无访问权限问题解决方法,造成这个问题...

mbzhong
38分钟前
1
0
Rabbitmq---消息队列

一 . MQ:message queue   消息队列的作用:   1 通信解耦   2 高峰限流 原理分析: 一开始,认证系统是强耦合的,A系统传递认证系统消息接收计算结果的过程中   1 传给认证系统   2 认...

Ala6
42分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部