8944: DP31 买卖股票的最好时机 II
[Creator : ]
Description
假设你有一个数组 prices，长度为 n，其中 prices[i] 是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回 0
3. 假设买入卖出均无手续费
Input
第一行输入一个正整数 n ，表示数组 prices 的长度
第二行输入 n 个正整数，表示数组中 prices 的值
Output
输出最大收益
Constraints
$0≤n≤1×10^5$
$1≤prices[i]≤10^4$
$1≤prices[i]≤10^4$
Sample 1 Input
7
8 9 2 5 4 7 1
Sample 1 Output
7
在第1天(股票价格= 8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7
Sample 2 Input
5
5 4 3 2 1
Sample 2 Output
0
由于每天股票都在跌，因此不进行任何交易最优。最大收益为0
Sample 3 Input
5
1 2 3 4 5
Sample 3 Output
4
第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。
HINT
相同题目：牛客网。