8945: DP32 买卖股票的最好时机 III
[Creator : ]
Description
假设你有一个数组 prices，长度为n，其中 prices[i] 是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回 0
3. 假设买入卖出均无手续费
1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回 0
3. 假设买入卖出均无手续费
Input
第一行输入一个正整数 n ，表示数组 prices 的长度
第一行输入 n 个正整数，表示数组 prices 的所有元素的值
Output
输出最大收益
Constraints
$1≤n≤10^5$
$$1≤price_i≤10^4$
$$1≤price_i≤10^4$
Sample 1 Input
6
8 9 3 5 1 3
Sample 1 Output
4
第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。
Sample 2 Input
4
9 8 4 1
Sample 2 Output
0
Sample 3 Input
5
1 2 8 3 8
Sample 3 Output
12
第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。
因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。
HINT
相同题目：牛客网。