首页 > 试题广场 >

低买高卖

[编程题]低买高卖
  • 热度指数：704 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}你已完全掌握未来 n 天某支股票的收盘价，其中第 i 天的股价为 p_i 。每天你至多操作一次，且每次仅能买入或卖出 1 股，或选择什么也不做。初始时你手中没有股票，也无法做空；第 n 天收盘时，你必须再次清空手中的股票。
\hspace{15pt}请设计出一套买卖计划，使得最终获得的收益最大，并输出该最大收益。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(2 \leqq n \leqq 3 \times 10^5\right) ，表示预测的天数。
\hspace{15pt}第二行输入 n 个整数 p_1, p_2, \dots, p_n\left(1 \leqq p_i \leqq 10^6\right) ，表示某支股票第 i 天的收盘价。


输出描述:
\hspace{15pt}输出一个整数，表示在最优买卖策略下，第 n 天结束时可以获得的最大收益。
示例1

输入

9
10 5 4 7 9 12 6 2 10

输出

20

说明

\hspace{15pt}一种可行且最优的操作方式如下：
\hspace{23pt}\bullet\, 第 2 天股价为 5 时买入 1 股；
\hspace{23pt}\bullet\, 第 3 天股价为 4 时买入 1 股；
\hspace{23pt}\bullet\, 第 5 天股价为 9 时卖出 1 股；
\hspace{23pt}\bullet\, 第 6 天股价为 12 时卖出 1 股；
\hspace{23pt}\bullet\, 第 8 天股价为 2 时再买入 1 股；
\hspace{23pt}\bullet\, 第 9 天股价为 10 时卖出 1 股。
\hspace{15pt}总收益为 (9-5)+(12-4)+(10-2)=20 。
算法知识视频讲解
添加回答
牛客548524361号头像 牛客548524361号
标准答案都是错的，一堆人跑那抄
发表于 今天 11:33:48 回复(0)
提交观点

问题信息

难度：
1条回答 27浏览

热门推荐

相关试题

低买高卖

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号