【Best Time to Buy and Sell Stock】cpp
2024-08-29 11:44:27
题目:
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size()==) return ;
int min_price = prices[], max_profit = ;
for ( size_t i = ; i < prices.size(); ++i )
{
min_price = std::min(min_price, prices[i]);
max_profit = std::max(max_profit, prices[i]-min_price);
}
return max_profit;
}
};
tips:
Greedy
核心在于维护两个变量:
min_price: 算上当前元素的最小值
max_profit:算上当前元素的最大利润
走完所有元素,可以获得max_profit
================================================
第二次过这道题,犹豫了一下才想起来思路。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int globalProfit = ;
if ( prices.empty() ) return globalProfit;
int minPrice = prices[];
for ( int i=; i<prices.size(); ++i )
{
minPrice = min(minPrice, prices[i]);
globalProfit = max(globalProfit, prices[i]-minPrice);
}
return globalProfit;
}
};
最新文章
- 谈一谈IOC、DI
- Linux系统管理命令之用户管理
- JAVA多线程实现的三种方式
- mysql事务,SET AUTOCOMMIT,START TRANSACTION
- Struts2 的ModelDriven理解
- android TextView 垂直滚动 用动画实现
- ckplayer网页播放器简易教程
- ByteBuffer的allocate和allocateDirect
- edgerouter bonding
- 修改本地配置远程连接oracle数据库
- 9. Palindrome Number 回文 my second leetcode 20170807
- 为什么使用SLF4J?
- 使用 dom4j 处理 xml (3)
- 转--select/poll/epoll到底是什么一回事
- 机器学习&;深度学习基础(机器学习基础的算法概述及代码)
- msm8909平台JEITA配置和bat-V therm表合入
- 【API】恶意样本分析手册——API函数篇
- learn python the hard way习题31~40总结以及列表的扩展知识
- Mybatis的枚举处理器
- 使用cnpm代替npm
热门文章
- JAVA 与 sqlite3 连接
- EasyUI整理学习
- 【Quartus错误】Internal Error: Sub-system: AMERGE
- [Java]在xp系统下java调用wmic命令获取窗口返回信息无反应(阻塞)的解决方案
- 利用临时表实现CTE递归查询
- hdu-2066 一个人的旅行---模板题
- 自动释放池的前世今生 ---- 深入解析 autoreleasepool
- 【转】VS2010发布、打包安装程序(超全超详细)
- DLM分布式锁的实现机制
- java基础面试题:说说&;和&;&;的区别