每日算法系列【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
目录
打赏
0
0
0
0
14
分享
相关文章
|
4月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
59 0
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
47 2
|
6月前
|
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
81 6
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
69 1
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
94 1
|
6月前
|
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
81 0
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
146 2

热门文章

最新文章