手撕代码:leetcode 309最佳买卖股票时机含冷冻期
转载于:https://segmentfault.com/a/1190000014746613
给定一个整数数组,其中第i个元素代表了第i天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
*你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
*卖出股票后,你无法在第二天买入股票(即冷冻期为1天)
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路和代码
这里转述leetcode上一个非常漂亮的解答。
在第i天时,我们可以进行三种操作,抛出或是买入或是啥都不干。但是具体下来,又有四种情况:
1.在持有一只股票的时候抛出
2.在持有一只股票的时候啥都不干
3.在持有0只股票的时候啥都不干
4.在持有0只股票的时候买入
而这些操作之间又存在潜在的联系,也就是说我如果在第i天进行以上四种操作之一,那么意味着我在第i-1天一定进行了四种操作中的某一种,从而支持我第i天的操作。具体关联如下:
1.第i天之行的操作:在持有一只股票的时候抛出=>在第i-1天执行的操作:在持有一只股票的时候啥都不干/在持有0只股票的时候买入
2.第i天执行的操作:在持有一只股票的时候啥也不干=>在第i-1天执行的操作:在持有一只股票的时候啥也不干/在持有0只股票的会后买入
3.第i天执行的操作:在持有0只股票的时候买入=>在第i-1天执行的操作:在持有0只股票的时候啥也不做
4.第i天执行的操作:在持有0只股票的时候啥也不做=>在第i-1天执行的操作:在持有0只股票的时候啥也不做/在持有一只股票的时候抛出
我们采用动态规划的思想,分别记录第i-1天的时候这四种情况的最大收入,并由此比较并得出第i天时这四种情况的最大收入。最后比较最后一天这四种情况可以得到的最大收益,代码如下:
1 int maxProfix(int prices[],int size)
2 {
3 if(size==0)return 0;
4 int hasOneDoNothing=-prices[0];
5 int hasOneSellIt=0;
6 int hasZeroDoNothing=0;
7 int hasZeroBuyOne=-prices[0];
8 for (int i = 0; i <size ; ++i) {
9 int tmp1=hasOneDoNothing;
10 int tmp2=hasOneSellIt;
11 int tmp3=hasZeroDoNothing;
12 int tmp4=hasZeroBuyOne;
13 hasOneDoNothing=tmp1>tmp4?tmp1:tmp4;
14 hasOneSellIt=(tmp1>tmp4?tmp1:tmp4)+prices[i];
15 hasZeroDoNothing=tmp2>tmp3?tmp2:tmp3;
16 hasZeroBuyOne=tmp3-prices[i];
17 }
18 return hasZeroDoNothing>hasOneSellIt?hasZeroDoNothing:hasOneSellIt;
19 }
这里你可能会困惑,为什么只比较 在最后一天持有0只股票并且不进行任何操作 和 在最后一天持有股票并抛出这两种情况呢?
假设我们最后一天持有股票并且不抛出,那么意味着在之前买入最后一只股票的那一天,如果我们不购入将会得到更大的收益。因此抛出一定比不抛出得到的损失小。
至于另一种情况,即最后一天又买入了股票,显然它一定比不买入股票得到的收益少啊。
因此我们只要比较最初提出的两种情况即可。
最新文章
- Spring学习记录(三)---bean自动装配autowire
- (进阶篇)PHP实现用户注册后邮箱验证,激活帐号
- 向Web开发人员推荐12款优秀的 Twitter Bootstrap 组件和工具
- poj 1442 名次树
- 中石油-高精度除法-java版
- Java 如何快速序列化
- 怎样去掉FireFox的导入向导
- ACM2033
- 字符串匹配的python实现
- kvm安装及配置
- JspSmart文件上传与下载
- ValidationMessageFor验证
- Nginx反向代理、CORS、JSONP等跨域请求解决方法总结
- Hadoop安全机制之令牌
- 使用邮件激活授权/ LightningChart license
- PHP Xdebug + PhpStorm调试远程服务器代码
- JavaScript前端面试题总结
- Spark分布式编程之全局变量专题【共享变量】
- 【Leetcode】338. Bit位计数
- webp图片优化