专栏首页算法码上来每日算法系列【LeetCode 714】买卖股票的最佳时机含手续费

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

题目描述

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

你可以无限次地完成交易,但是你每次交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

示例1

输入:
prices = [1, 3, 2, 8, 4, 9], fee = 2
输出:
8
解释:
能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

提示

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

题解

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

这题其实就是在系列题目第二题基础上加了个手续费,也就是无限次买卖股票,但是每次卖的时候都得交一笔手续费。

这时候就不能和第二题一样,每次连续上升子区间都买卖一次了,因为如果买卖一次都不够交手续费的话,就不能进行买卖。或者一段连续下降子区间的差值小于手续费,那么就得把这段下降子区间也包含进去,前后只卖买一次。

所以我们换个思路,还是沿用第四题的动态规划思路。令 为第 只股票之前(包含)买卖(最后一次操作是买)可以获得的最大利润, 为第 只股票之前(包含)买卖(最后一次操作是卖)可以获得的最大利润。那么类似的有如下转移方程:

初始情况就是 和 。

此外这里还可以优化去掉一个维度,因为每个时刻状态只与前一个时刻有关。

时间复杂度是 。

代码

python

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp0, dp1 = -prices[0], 0
        for p in prices[1:]:
            dp1 = max(dp1, dp0+p-fee)
            dp0 = max(dp0, dp1-p)
        return dp1

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

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    本题中买卖次数变成了最多两次,那么我们可以照搬之前只能买卖一次的做法。首先如果我们假设第一只股票卖出去时价格是 ,那么它之前的最优买入价格(也就是最低的价格)...

    godweiyang
  • 每日算法系列【LeetCode 309】最佳买卖股票时机含冷冻期

    设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

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

    设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

    godweiyang
  • 如何将 Oracle 单实例数据库转换为RAC数据库?

    墨墨导读:本文来自墨天轮用户投稿,文章详述安装一套RAC环境,并把单实例数据库通过通过rman还原到这个环境(通常如果是生产环境,我们会搭建从RAC到单实例数据...

    数据和云
  • 像监听页面一样监听戈多的动态

    不知道各位童鞋有木有看过 《等待戈多》 这部出名的荒诞戏剧 。其剧情大概就是 戈戈 与 狄狄 等待 戈多 的过程中发生的一些琐事,一共两幕。等了这么多年,也不知...

    陈大鱼头
  • 从句的分类与做题方法

    白胡杨同学
  • 基于UDP/IP协议的电口通信(二)

    上一篇对整个UDP/IP协议的电口通信设计有个整体了解,接下来就是对于每个模块的设计,这部分,计划用两篇文章完成,会尽量简洁一点,谢谢大家支持。

    碎碎思
  • 哈夫曼编码和数据压缩Java

    第二步:创建新的HFMTreeNode, 在优先队列里面添加每一个Huffman Node

    成都小展
  • 干货技巧 | phpinfo信息利用

    php扩展的路径,图省事没用lamp包有点捞…(这里还是说下linux不推荐用phpstudy,很多linux装了phpstudy系统会崩)

    HACK学习
  • root cause why relocation in CRM will cause replication failure in 03

    版权声明:署名,允许他人基于本文进行创作,且必须基于与原先许可协议相同的许可协议分发本文 (Creative Commons)

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券