【LeetCode】122. Best Time to Buy and Sell Stock II
2024-10-18 23:33:21
题目:
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
提示:
此题应使用贪心算法的思想。我所采用的贪心规则如下:
- 从第一个元素开始遍历至最后一个元素;
- 若下一个元素比当前元素大,那么就抛售;并以下一个元素的价钱买入,同时累加利润;
- 若下一个元素比当前元素小,那么就以下一个元素的价钱买入(若连续出现递减的情况,那么最后的买入价格是最后那个最小的元素);
代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == ) return ;
int buy_in = prices[], sum = ;
for (int i = ; i < prices.size(); ++i) {
if (prices[i] > buy_in) {
sum += prices[i] - buy_in;
buy_in = prices[i];
} else {
buy_in = prices[i];
}
}
return sum;
}
};
后来在论坛上发现了更加简洁的解法,核心思想其实是比较类似的:
int maxProfit(vector<int> &prices) {
int ret = ;
for (size_t p = ; p < prices.size(); ++p)
ret += max(prices[p] - prices[p - ], );
return ret;
}
其实就是只要有涨就先卖再买,但是这种解法更加简洁清楚。
最新文章
- 【转载】 Java线程面试题 Top 50
- plist文件的使用
- Android开发在路上:少去踩坑,多走捷径
- Js_字符串操作
- 文件操作II
- 使用Google Cloud Platform构建机器学习项目-宠物识别
- 计蒜客NOIP模拟赛6 D1T1Diamond-square
- 如何在joomla上展示word,pdf,xlsx,ppt
- Biorhythms POJ - 1006 中国剩余定理
- BZOJ1799 self 同类分布 数位dp
- csharp: DefaultValueAttribute Class
- 5.27 Test
- shell 脚本的时间差计算
- Windows消息循环
- MySQL:按前缀批量删除表格
- Nginx实践03-配置虚拟主机的3种方式
- 传智:自己简单实现一个struts2框架的demo
- 可以在命令行直接使用密码来进行远程连接和远程拉取文件的命令:sshpass
- VS2013新特性
- SVN增加文件后,文件无法自动包括在项目中的原因