【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
1 题目
给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
2 解析
-
对于 第一个状态 d 1 d_1 d1,我们目前持有的这一支股票可以是在第 i−1 天就已经持有的,对应的状态为 d 1 d_1 d1;或者是第 i 天买入的,那么第 i−1 天就不能持有股票并且不处于冷冻期中,对应的状态为 d 3 d_3 d3加上买入股票的负收益 prices[i]。因此状态转移方程为:(理解为买入状态)
d 1 = m a x ( d 1 , d 3 − p r i c e s [ i ] ) d_1=max(d_1,d_3−prices[i]) d1=max(d1,d3−prices[i]) -
对于第二个状态 d 2 d_2 d2,我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票,那么说明在第 i−1 天时我们必须持有一支股票,对应的状态为 d 1 d_1 d1加上卖出股票的正收益 prices[i]。因此状态转移方程为:(理解为卖出)
d 2 = d 1 + p r i c e s [ i ] d_2=d_1+prices[i] d2=d1+prices[i] -
对于第三个状态 d 3 d_3 d3,我们在第 i 天结束之后不持有任何股票并且不处于冷冻期,说明当天没有进行任何操作,即第 i−1 天时不持有任何股票:如果处于冷冻期,对应的状态为 d 2 d_2 d2;如果不处于冷冻期,对应的状态为 d 3 d_3 d3。因此状态转移方程为:
d 3 = m a x ( d 2 , d 3 ) d_3=max(d_2,d_3) d3=max(d2,d3)
3 Python实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
d_1,d_2,d_3 =-prices[0],0,0
for i in range(1,len(prices)):
# 买入
tmp_d_1 = max(d_1,d_3-prices[i])
# 已经卖出
tmp_d_2 = d_1+prices[i]
# 冻结
tmp_d_3 = max(d_2,d_3)
d_1,d_2,d_3 = tmp_d_1,tmp_d_2,tmp_d_3
return max(d_2,d_3)
相关文章
- python后端面试第四部分:django框架--长期维护
- python模块typing的作用
- Python 刷Leetcode题库,顺带学英语单词(13)
- python操作docker SDK:Docker SDK for Python
- Python:利用pip/conda命令导出/安装当前环境所有的依赖包及其对应的版本号、在新的环境中安装导出的包之详细攻略
- 〖Python接口自动化测试实战篇⑥〗- 接口抓包工具 Chrome 的使用
- Python爬虫基础讲解:数据持久化——json 及 CSV模块简介
- 【Python成长之路】python 基础篇 -- global/nonlocal关键字使用
- Python 最频繁使用的4个函数:lambda、 map、filter 和 reduce
- 【项目实战】Python实现xgboost分类模型(XGBClassifier算法)项目实战
- 【LeetCode Python实现】7. 整数反转(中等)
- 【LeetCode Python实现】375. 猜数字大小 II(中等)
- 【华为OD机试 2023】完美走位(C++ Java JavaScript Python)
- python 代码小技巧之一行代码转换列表中的数据并实现运算
- Python简单图片爬虫
- Python编程:time和datetime时间模块详解
- Python:mysql-connector-python模块对MySQL数据库进行增删改查
- Python开发学习之Python用三十行代码,打造一款简单的人工语音对话
- 【Leetcode刷题Python】生词本单词整理
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- Python kafka操作实例(kafka-python)