专栏首页算法码上来每日算法系列【LeetCode 123】买卖股票的最佳时机 III

每日算法系列【LeetCode 123】买卖股票的最佳时机 III

题目描述

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例1

输入:
[3,3,5,0,0,3,1,4]
输出:
6
解释:
在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例2

输入:
[1,2,3,4,5]
输出:
4
解释:
在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。  
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例3

输入:
[7,6,4,3,1]
输出:
0
解释:
在这个情况下, 没有交易完成, 所以最大利润为 0。

题解

这是 【买卖股票的最佳时机】 系列题目的第三题。

本题中买卖次数变成了最多两次,那么我们可以照搬之前只能买卖一次的做法。首先如果我们假设第一只股票卖出去时价格是 ,那么它之前的最优买入价格(也就是最低的价格)计算方法和第一题相同,只需要用一个变量存储就行了。而第二次买卖我们只需要知道 右边进行一次买卖最多能赚到多少钱就行了。这可以通过从右向左倒过来预处理处理,方法和第一题完全相同。

记第 只股票左边(包含)买卖一次最大利润为 ,右边(包含)买卖一次最大利润为 ,那么最终的答案就是:

时间复杂度是 。

代码

python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0
        dp = [0] * n
        minn = prices[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1], prices[i]-minn)
            minn = min(minn, prices[i])
        maxx, maxp, res = prices[-1], 0, max(dp)
        for i in range(n-2, 0, -1):
            maxp = max(maxp, maxx-prices[i])
            maxx = max(maxx, prices[i])
            res = max(res, dp[i-1]+maxp)
        return res

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法系列【LeetCode 188】买卖股票的最佳时机 IV

    令 为第 只股票之前(包含)买卖 次(且最后一次操作为买入)可以获得的最大利润, 为第 只股票之前(包含)买卖 次(且最后一次操作为卖出)可以获得的最...

    godweiyang
  • 每日算法系列【LeetCode 714】买卖股票的最佳时机含手续费

    给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。

    godweiyang
  • 每日算法系列【LeetCode 121】买卖股票的最佳时机

    如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

    godweiyang
  • jqm文件上传,上传图片,jqm的表单操作,jqm的ajax的使用,jqm文件操作大全,文件操作demo

    最近在论坛中看到,在使用html5中上传图片或文件,出现各种问题。这一方面,我也一直没有做过,今天就抽出了一点时间来学习一下...

    业余草
  • 【应用】信用评分卡:高级分析

    当一位年轻的商业分析师向我们讲述他最近回家的事件时,充满分析师的房间爆发出一阵响亮的笑声。 一位遥远的阿姨询问了他的新职业。 他的回答 - 我正在进行建模。 她...

    陆勤_数据人网
  • 【MOOC】Python网络爬虫与信息提取

    Python网络爬虫与信息提取-北京理工大学-嵩天 发布大学:北京理工大学 发布课程:Python网络爬虫与信息提取 授课老师:嵩天 课程简介:“The web...

    一点儿也不潇洒
  • 企业应如何运用ERP系统的BOM表?

      在制造企业应用ERP过程中,为了降低库存、减少成本,物料控制部按照只会BOM来做,但由于BOM的难以制定,常会造成BOM表还没制定出来生产部就已经在开始生产...

    用户5495712
  • 白天写代码,晚上摆地摊!9年前摆地摊学会了这些道理...

    两会期间李克强总理说了一番话,温暖了无数个像我一样的底层人民,他说:一味追求整洁,不让开小店,是懒政,政府必须要提高规划、管理的能力,决不能光图省事,一禁了之,...

    Java中文社群_老王
  • 学BOM绝佳资料!

    导读:本文将就静态数据中物料清单(BOM)的作用,结合CAD(计算机辅助设计)、CAPP(计算机辅助工艺编制)、PDM(产品数据管理)、MRPⅡ(物造资源计划)...

    用户5495712
  • 京东海量订单处理

    2014年的618显得和以往任何店庆促销日都不同,不仅仅是因为电子商务本身在中国不断飞速发展对京东系统带来的挑战,更为重要的是2014年5月22日刚走入美国纳斯...

    后端技术探索

扫码关注云+社区

领取腾讯云代金券