lintcode-151-买卖股票的最佳时机 III
2024-08-25 20:21:39
151-买卖股票的最佳时机 III
假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。
注意事项
你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)
样例
给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6
标签
前后遍历 枚举法 数组
思路
使用前后遍历，分别求出 0-i 的最大值和 i+1-size-1 的最大值。
left[i] 表示0 - i 这段数组的最大收益
right[i] 表示i - A.length-1 这段数组的最大收益
code
class Solution {
public:
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
// write your code here
int size = prices.size();
if(size <= 0) {
return 0;
}
int max = 0, i = 0, min = 0;
vector<int> left(size, 0);
vector<int> right(size, 0);
min = prices[0];
for(i=1; i<size; i++) {
if(prices[i] >= min) {
left[i] = (left[i-1] > prices[i]-min) ? left[i-1] : prices[i]-min;
}
else {
left[i] = left[i-1];
min = prices[i];
}
}
max = prices[size-1];
for(i=size-2; i>=0; i--) {
if(prices[i] <= max) {
right[i] = (right[i+1] > max-prices[i]) ? right[i+1] : max-prices[i];
}
else {
right[i] = right[i+1];
max = prices[i];
}
}
max = INT_MIN;
for(i=0; i<size; i++){
max = (max > left[i]+right[i]) ? max : left[i]+right[i];
}
return max;
}
};
最新文章
- C语言中的system函数参数及其作用
- Django知识(二)
- webstrom 中启用emmet插件的方法
- C# params关键字
- 企业服务总线（ESB）
- Git - Download for Linux and Unix
- Spring框架
- 学习之路十四：客户端调用WCF服务的几种方法小议
- PowerShell入门（一）：PowerShell能干什么？
- SQL增删改语句
- Python开发爬虫之BeautifulSoup解析网页篇：爬取安居客网站上北京二手房数据
- 算法笔记--Splay && Link-Cut-Tree
- java 第三周作业
- Android UI（五）云通讯录项目之联系人列表，带侧滑选择，带搜索框
- SQL Server查询数据库所有存储过程、触发器、索引信息SQL分享
- UITableView取消cell选中状态关于deselectRowAtIndexPath
- mybatis 使用merge into
- Error:java: 无效的源发行版: 1.8
- Active Learning
- 10个最受欢迎的Java类（转)