题目描述

给定⼀个数组prices ，它的第 i 个元素 prices[i] 表⽰⼀⽀给定股票第 i 天的价格。

你只能选择 某⼀天 买⼊这只股票，并选择在 未来的某⼀个不同的⽇⼦ 卖出该股票 。设计⼀个算法来计算你所能获取的最⼤利润。返回你可以从这笔交易中获取的最⼤利润 。如果你不能获取任何利润 ，返回 0 。

输入格式

输入n,表示一共有n天的股票数据（N<=10^{5}）

输入n个数据，表示⼀⽀给定股票每天价格(股票价格不能超过10000)。

输出格式

输出你可以从这笔交易中获取的最⼤利润 。如果你不能获取任何利润 ，返回 0 。

输入样例 #1

6
7 1 5 3 6 4

输出样例 #1

5

输入样例 #2

5
7 6 4 3 1

输出样例 #2

0

输入样例 #3

2
1 10000

输出样例 #3

9999

提示

请分别用暴力破解、贪心算法、动态规划解决此问题

数据范围

输入n,表示一共有n天的股票数据（N<=10^{5}