Leetcode - 买卖股票的最佳时机
发布日期:2021-07-01 00:14:58
浏览次数:2
分类:技术文章
本文共 923 字,大约阅读时间需要 3 分钟。
题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解题思路
该题解法和最大连续子数组和的解法思路是一样的。
1、根据股票的利益意义,想要更多利益则值低时买进,值高时卖出。根据提供的股票价格不方便得出股票价格变化,对原数据进行计算:list[i] - list[i-1] = 股票的变化。变化为正时股票增长(存在利益),变化为负时股票为下跌(无利益)。
2、得到股票的变化值列表,即求最大子数组和,最后得到正解。
#define max(a, b) a > b ? a : bint maxProfit(int* prices, int pricesSize) { int max=0,s, i, j, dp[1000010], nums[1000010]; for (i = 0; i < pricesSize - 1; i++) nums[i] = prices[i + 1] - prices[i]; max = dp[0] = nums[0]; if (max < 0) max = 0; for (int i = 1; i < pricesSize - 1; i++) { if (dp[i - 1] < 0) dp[i - 1] = 0; dp[i] = dp[i - 1] + nums[i]; max = max(max, dp[i]); } return max;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84258591 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月20日 09时16分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
跟踪sys_mkdir的系统调用过程
2019-05-01
Linux系统fork执行过程
2019-05-01
跟踪sys_execve的执行过程
2019-05-01
分析schedule()的执行过程
2019-05-01
Linux内核学习收获
2019-05-01
optirun执行错误的解决办法
2019-05-01
pycharm无法识别pyqt的问题
2019-05-01
STLPort 哈希表 hash_map/hash_multimap 删除速度慢
2019-05-01
deepin系统没有声音的解决方法
2019-05-01
python学习笔记
2019-05-01
Ant内置任务之replace
2019-05-01
Ant内置任务之tstamp
2019-05-01
Ant内置任务之whichresource
2019-05-01
Ant内置任务之touch
2019-05-01
Ant内置任务之truncate
2019-05-01
Ant内置任务之sync
2019-05-01
Ant内置任务之symlink
2019-05-01
Ant内置任务之sound
2019-05-01
Ant内置任务之typedef
2019-05-01