文档章节

188. Best Time to Buy and Sell Stock IV

cofama
 cofama
发布于 2017/05/21 18:13
字数 922
阅读 6
收藏 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
2018/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
2018/04/01
0
0
LeetCode 309. Best Time to Buy and Sell Stock with Cooldown (在具有冻结时间条件下买入和卖出股票的最佳时间)

原题 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 transaction......

dby_freedom
2018/12/06
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
2018/10/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java B2B2C o2o多用户商城 springcloud架构-docker-feign-hystrix(六)

简介 上一节我们讨论feign的配置,这节我们讨论一下,feign+hystrix调用生产者时,进行容错处理 一、创建模块(microservice-consumer-movie-feign-with-hystrix) 二、pom.xml文件 <?xml ve...

sccspuercode
28分钟前
2
0
简单聊聊Linux学习经历

简单聊聊Linux学习经历 学习,是我们一生中都规避不了的一个话题,人的一生中都是在不断的学习,无论是功成名就的人士,还是一无是处的小混混,始终都处在一个不断学习的环境中,只是学习的内...

linuxCool
47分钟前
2
0
C++ This 详解

分类: C++ this 是 C++ 中的一个关键字,也是一个 const 指针,它指向当前对象,通过它可以访问当前对象的所有成员。 所谓当前对象,是指正在使用的对象。例如对于stu.show();,stu 就是当前...

天王盖地虎626
今天
3
0
如何自制一个Spring Boot Starter并推送到远端公服

概 述 传统的 Maven项目一般将需要被复用的组件做成 Module来进行管理,以便二次调用;而在 Spring Boot项目中我们则可以使用更加优雅的 Spring Boot Starter来完成这一切。 基于Spring Boot...

CodeSheep
今天
1
0
大数据教程(11.9)hive操作基础知识

上一篇博客分享了hive的简介和初体验,本节博主将继续分享一些hive的操作的基础知识。 DDL操作 (1)创建表 #建表语法CREATE [EXTERNAL] TABLE [IF NOT EXISTS] table_name [(col_name ...

em_aaron
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部