[Leetcode] 第309题 最佳买卖股票时机含冷冻期
2024-09-01 10:28:44
一、题目描述
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
二、题目分析
1)动态规划题目,和最佳买卖股票时机III和IV类似,需要保存两种状态
2)buy[i]代表第i天不卖股票的最大利润,sell[i]代表第i天不买股票的最大利润
3)那么buy[i]=max(buy[i-1],sell[i-2]-prices[i]);第一项代表不买股票,也就是什么也不做,和前一天不卖的状态一致,第二项代表买股票,因为有冷冻期,那么应该是前两天卖出得到的钱减去当天的股票价格
4)同理,sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
5)其实就是分别找到距离buy[i]和sell[i]最近的两个状态,就是buy[i-1],sell[i-2]和sell[i-1],buy[i-1]
6)不过需要注意初始状态,第一天卖出初始化为0,买入需要初始化为-prices[0],
7)并且需要注意buy在第二天的状态,此时sell[i-2]应该用0代替
8)最终状态,肯定是最后一次卖出的时候利润最大
三、代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (!n)return ;
vector<int>buy(n), sell(n);
buy[] = -prices[];
sell[] = ;
for (int i = ; i < n; ++i) {
sell[i] = max(sell[i - ], buy[i - ] + prices[i]);
if (i < )
buy[i] = max(buy[i - ], -prices[i]);
else buy[i] = max(buy[i - ], sell[i - ] - prices[i]);
}
return sell[n - ];
}
};
最新文章
- JavaScript的理解记录(6)
- Android-SQLite版本问题
- js中同步与异步请求方式
- Cisco IOS IP Service Level Agreementv (IP SLA)
- linux tricks 之 bitmap分析.
- log4net按等级多种方式记录日志
- EasyUI ComboBox默认值
- .net mvc HtmlHelper扩展使用
- React-Native错误笔记-EPERM
- VB 活动添加item元素
- android layout的布局
- [android]Gradle: 执行失败的任务 &#39;: processDebugManifest&#39;
- Jquery遍历数组之$.inArray()方法介绍
- SOA 下实现分布式 调用 cxf+ webService +动态调用
- 我的Spring Boot学习记录(一):自动配置的大致调用过程
- SQL Server中LIKE %search_string% 走索引查找(Index Seek)浅析
- 清除float影响
- 用多线程处理FTP上传
- SpringSecurity实现图形验证码功能
- hadoop客户端如何配置
热门文章
- centos7.x 安装系统/配置网络/设置主机名
- abp(net core)+easyui+efcore实现仓储管理系统——使用 WEBAPI实现CURD (十五)
- Nacos(八):Nacos持久化
- 人脸识别Demo
- RANSAC简史(一)——RANSAC之初
- Unity/C#基础复习(5) 之 浅析观察者、中介者模式在游戏中的应用与delegate原理
- ASP.NET Core 2.2 : 二十七. JWT与用户授权(细化到Action)
- CodeForces 1107 F Vasya and Endless Credits
- lightoj 1105 - Fi Binary Number(dp+思维(斐波那契))
- 2018 Multi-University Training Contest 1(部分题解)