Problem B: 买卖股票的最好时机

Problem B: 买卖股票的最好时机

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 20  Solved: 16
[Submit] [Status] [Web Board] [Creator:]

Description

假设有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益。
1、你只能买入一次股票和卖出一次股票,并非每天都可以买入和卖出,总共只能买入和卖出各一次,且买入只能在买入的前面某一天。
2、如果不能获取到任何利润,请返回0
3、假设买入和卖出均无手续费


程序先输入的是长度n
后面一行是n个数字代表每一天的价格

Input

7
8 9 2 5 4 7 1

Output

5

Sample Input

3
2 4 1

Sample Output

2

HINT

假如输入是:
7
8 9 2 5 4 7 1
这种情况下,在第3天(股票价格是2)的时候买入,在第6天(股票价格是7)的时候卖出,最大利润=7-2=5
不能选择在第2天买入,第3天卖出,这样就亏损7块钱;同时,你也不能在买入钱卖出股票。
所以最后输出是
5

[Submit][Status]