文档章节

188. Best Time to Buy and Sell Stock IV

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

© 著作权归作者所有

共有 人打赏支持
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 Buy and Sell Stock with Transaction Fee

问题: Your are given an array of integers , for which the -th element is the price of a given stock on day ; and a non-negative integer representing a transaction fee. You may ......

叶枫啦啦
01/16
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
决战Leetcode: easy part(1-50)

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

qq_32690999
01/25
0
0
714. Best Time to Buy and Sell Stock with Transaction Fee。

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee. You......

Leafage_M
02/12
0
0
leetcode算法题解(Java版)-4-动态规划(杨辉三角问题)

一、简单模拟 题目描述 Say you have an array for which the i th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete ......

kissjz
04/29
0
0
121. Best Time to Buy and Sell Stock。

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one ......

Leafage_M
02/09
0
0
121. Best Time to Buy and Sell Stock(详解)

问题: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and se......

117
06/29
0
0
出售股票的最大利润 Best Time to Buy and Sell Stock

问题: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and se......

叶枫啦啦
2017/06/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Xamarin Essentials教程地理定位Geolocation

Xamarin Essentials教程地理定位Geolocation 通过地理定位功能,应用程序可以获取用户的当前地理位置,如经纬度值。利用地理位置,可以在地图上定位,也可以转化物理位置,划分用户的归属地。...

大学霸
11分钟前
0
0
vue 编译警告 Compiled with 4 warnings

There are multiple modules with names that only differ in casing. This can lead to unexpected behavior when compiling on a filesystem with other case-semantic. Use equal casing.......

落雪飞声
15分钟前
0
0
开篇文章,长期记录安全情形

密码位置 密码位于注释中 密码位于服务器端文件中 通过访问根目录下.htaccess、robots.txt查看禁查路径 密码文件可能存在的路径:/、/extra/、/extras/ 密码加密 binary to base16 sha256 彩虹...

hirainn
28分钟前
0
0
mysql数据库设置root可以远程登录的方法

mysql数据库设置root可以远程登录的方法 Posted on 2018-02-21 21:08 sishuisufeng 阅读(161) 评论(0) 编辑 收藏 允许root用户在任何地方进行远程登录,并具有所有库任何操作权限,具体操作如...

rootliu
33分钟前
0
0
TensorFlow 图的基本操作

图的创建,一般只需要使用默认图就能满足大部分的需求了 # 1 创建图的方法# 在默认图中创建常量c = tf.constant(0.0)# 新建一个图g = tf.Graph()# 设置上下文管理器,标明操作...

阿豪boy
今天
0
0
git 忽略文件失效

git update-index --assume-unchanged */.project

林子大鸟
今天
1
0
实现验证码功能

1、实现验证码,并存储 import com.dtb.pc_enterprise.entity.EnterUserEntity;import com.dtb.pc_enterprise.service.AdminService;import com.dtb.pc_enterprise.util.RedisService;......

木九天
今天
0
0
iptables 实例

以下部分内容为网络查询并整理结果 filter表小案例 iptables规则五条链:PREROUTING,INPUT,FORWARD,OUTPUT,POSTROUTING 四个表:filter nat mangle raw ###netfilter和iptables说明: 1、 ne...

李超小牛子
今天
0
0
Java面试基础篇——第六篇:常见Map类的区别

常见的map类有: HashMap, ConcurrentHashMap (Jdk1.8) , LinkedHashMap, TreeMap, Hashtable。 其中我们最常用的莫过于HashMap, 和并发情况下使用的ConcurrentHashMap了,它们的主要区别就在...

developlee的潇洒人生
今天
2
0
spring-boot:run启动时,指定spring.profiles.active

Maven启动指定Profile通过-P,如mvn spring-boot:run -Ptest,但这是Maven的Profile。 如果要指定spring-boot的spring.profiles.active,则必须使用mvn spring-boot:run -Drun.profiles=test......

夜黑人模糊灬
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部