leetcode第一刷_Best Time to Buy and Sell Stock III
2024-08-29 12:00:56
这道题还是挺难的,属于我前面提到的,给个数组,线性时间找出个什么东西,尽管上面的两个买卖股票也是这类。只是相比之下稚嫩多了。有关至少至多的问题比較烦人,不好想,等再做一些题,可能会发现什么规律。这道题的情况还是比較少的,要么买卖了两次。要么一次。
买卖一次的情况,已经解决过了,如今分析买卖两次的情况。
两次买卖之间是没有交叉的,即下一次买之前一定已经卖掉了。最easy想到,穷去分点,每一个部分都依照买卖一次的方法做。
好,恭喜。你已经走在超时的路上了。那么怎么办呢。有没有一种方法,在线性时间内,等我走到一个分点的时候,就能知道划分两次求出来的结果?
没错。辅助空间。先从头往后扫一遍,记录下以这个点为终点时的最大收入,然后从尾向头扫一遍。记录下以这个点为起点的最大收入。
再对每一个分点扫一遍,看看已他为起点终点算出来的交易收入是不是最优的。
思路是这种。描写叙述起来比較清晰。实现的时候还是有能够优化的地方的,比如你发现从尾向头扫描的结果根本不用一整个数组。仅仅要保存好后一个位置的最优值就能够了。由于当前最优值仅仅跟峰值与当前值以及过去最优相关。
代码例如以下。未优化空间:
class Solution {
public:
int maxProfit(vector<int> &prices) {
int len = prices.size();
if(len <= 1)
return 0;
vector<int> phistory(len);
vector<int> pfuture(len);
int valley = prices[0], peak = prices[len-1];
for(int i=1;i<len;i++){
valley = min(valley, prices[i]);
phistory[i] = max(phistory[i-1], prices[i]-valley);
}
int res = 0;
for(int i=len-2;i>=0;i--){
peak = max(peak, prices[i]);
pfuture[i] = max(pfuture[i+1], peak-prices[i]);
res = max(res, pfuture[i]+phistory[i]);
}
return res;
}
};
最新文章
- app的推广
- 网络请求的基本知识《极客学院 --AFNetworking 2.x 网络解析详解--1》学习笔记
- 最大ASCII的和问题
- css修改,类似elememt.style样式修改
- Dungeon Master 分类: 搜索 POJ 2015-08-09 14:25 4人阅读 评论(0) 收藏
- mac下U盘装机系统的制作(命令行)
- 热门Web开发方式 REST实现原理浅析
- ComboTree使用
- HDU--杭电--4504--威威猫系列故事——篮球梦--DP
- C语言学习之路,第一篇章。
- [置顶] Ants(Northeastern Europe 2007)
- Node.js学习 - CallBack Function
- curl中通过json格式吧post值返回到java中遇到中文乱码的问题
- Android 开发TCP协议时,报错NetworkOnMainThreadException
- Java笔试题库之选题题篇【71-140题】
- SQLServer之修改触发器
- STM32F103单片机解密资料
- JAVA经典面试题:讲一讲JVM的组成
- 设置HTML编码为UTF-8
- EFCore CodeFirst 适配数据库