问题 D: 买卖股票的最佳时机

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:12 解决:5

题目描述

给定一个数组 prices ,它的第 i 个元素 pricesi 表示一支股票在第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
  • 如果你无法获取任何利润(例如价格一直下跌),则返回 0 。
  • 注意:你不能在买入前卖出股票,且只能进行一次交易(买一次,卖一次)。

输入

  • 第一行包含一个整数 n ,表示天数(即数组的长度)。
  • 第二行包含 n 个整数,相邻整数之间用空格分隔,依次表示每天的价格 prices1,prices2,,pricesn 。

输出

输出一行,包含一个整数,表示能获取的最大利润。如果无法获利,输出 0 。

样例输入 复制

6
7 1 5 3 6 4

样例输出 复制

5