5791: 【系列题】股票问题(二)买卖股票的最佳时机 II

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

给你一个整数n,输入一个长度为n的数组,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

Input

输入一个n,表示数组长度

接下来一行输入n个数,表示股票每天的价格

Output

返回 你能获得的 最大 利润 。

Sample Input Copy

6 
7 1 5 3 6 4

Sample Output Copy

7

HINT

样例说明:

输入:prices = [7,1,5,3,6,4]

输出:7

解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。   随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。


数据范围:

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104