【LeetCode】309. 最佳买卖股票时机含冷冻期 结题报告 (C++)
原题地址:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 题目描述: 给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。? 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,2] 输出: 3? 解释: 对应的交易状态为: [买入,卖出,冷冻期,买入,卖出] 解题方案: 使用动态规划的方法解题,参考地址:https://blog.csdn.net/qq_17550379/article/details/82856452 这是股票系列问题中目前来看最难的一个,不过有了前面几个问题的思路,这个问题求解起来非常容易。首先,我们看到问题中提到了三种状态buy、sell和cooldown,那么我们脑中的第一个想法就是通过动态规划来解 如果我们index:i天为冷冻期,那么只能说明index:i-1天卖掉了股票,那么i天的收益和i-1天是一样的 cooldown[i]=sell[i-1] 如果我们考虑index:i天卖出,要求利润最大的话。那么无非是index:i-1之前就持有股票,所以index:i-1天也可以卖出,或者另一种情况就是index:i-1当天买入了股票。 sell[i]=max(sell[i-1],buy[i-1]+prices[i]) 如果我们考虑index:i天买入,要求利润最大的话。无非是index:i-1之前就不持有股票,我们要考虑哪天买,所以index:i-1也可以买入,或者另一种可能就是index:i-1天是冷冻期。 buy[i]=max(buy[i-1],cooldown[i-1]-prices[i]) 我们第一天不可能卖出或者冻结,那么这两个sell[0]=0 cooldown[0]=0,但是我们第一天可以买入啊,所以buy[0]=-prices[0]。还有一点要注意的就是,我们一定是最后一天卖出或者最后一天冻结利润最大。 代码: class Solution { public: int maxProfit(vector if (!prices.size()) return 0; vector buy[0] = -prices[0]; for (unsigned int i = 1; i < prices.size(); ++i) { cooldown[i] = sell[i - 1]; sell[i] = max(sell[i - 1],buy[i - 1] + prices[i]); buy[i] = max(buy[i - 1],cooldown[i - 1] - prices[i]); } return max(sell[prices.size() - 1],cooldown[prices.size() - 1]); } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- ruby-on-rails – 如果Sidekiq未处于运行状态,则自动启动它
- Code RO-data RW-data ZI-data KEIL MDK
- Ajax概念、HTTP请求概念、Ajax的原生和jQuery实现、跨域知识
- 使用C#.Net进行音频转换
- cocos2D-x3.4 新建项目的批处理文件
- Roope的Cocos2d-x学习之旅 004:动作一起做——Spawn和Sequ
- c – 我应该更喜欢一个函数中的常量:constexpr const或enu
- 微信开发,对象转换为xml时候引用XStream这个类报错处理方案
- [译] 翻译NSHipster,NSRegular?Expression 正则表达式
- c – void *和void **之间有什么区别?