AcWing 83 股票的最大利润
发布日期:2021-05-28 16:31:07 浏览次数:10 分类:技术文章

本文共 614 字,大约阅读时间需要 2 分钟。

题目描述:

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖 一次 该股票可能获得的利润是多少?

例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。

如果我们能在价格为5的时候买入并在价格为16时卖出,则能收获最大的利润11。

样例

输入:[9, 11, 8, 5, 7, 12, 16, 14]输出:11

分析:

暴力的方法是枚举买的天数和卖的天数,时间复杂度为平方级的。想降低复杂度就需要去掉一次枚举,假设去掉的是买的天数的枚举。设dp[i]为在第i天卖出可获得的最大收益,则dp[i] = a[i] - min(a[0] ~ a[i])。这里不用单独设置dp数组,直接使用ans记录最大利益即可。

class Solution {public:    int maxDiff(vector
& nums) { int n = nums.size(); if(!n) return 0; int p = nums[0],ans = 0; for(int i = 0;i < n;i++){ p = min(p,nums[i]); ans = max(ans,nums[i] - p); } return ans; }};

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/88642333 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 84 求1+2+…+n
下一篇:AcWing 82 圆圈中最后剩下的数字

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年02月21日 17时20分21秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章