解题思路

• 相关算法：贪心算法（或等价的两状态 DP）。 核心结论：把所有相邻两天的上涨差值都赚到手即可。对每个 i=1..n-1，若 prices[i] > prices[i-1]，就把差值 prices[i]-prices[i-1] 加入答案。将所有正差值求和就是最大收益。

• 实现要点：

  1. 一次遍历价格数组；
  2. 若今天价高于昨天，则把这一段利润累加；
  3. 遍历结束即为答案。 该思路等价于“把所有上升段拆成若干买入-卖出的子交易”，拆分或合并不影响总收益。

题目内容

用给定一个正整数及非负整数 $prices$ 的列表，第一个正整数表示 $prices$ 列表中数字的总个数，$prices$ 表示某个股票在每天的价格。

用户初始持有股票为 $0$ ，现在需要基于 $prices$ 的价格列表计算出如何买入卖出能够得到最大的现金收益。

其中要求每天仅能够持有一份股票，但是每天都可以将股票买入或者卖出，如果无法取得收益，返回的结果应该为 $0$ 。

示例：

6
715364

表示共有 $6$ 天的股票价格，第 $1$ 天到第 $6$ 天的价格分别为 $7$ $1$ $5$ $3$ $6$ $4$ 。

输出：

7

表示可以得到的最大收益为 $7$

方法为：在第 $2$ 天以 $1$ 的价格买入，第 $3$ 天以 $5$ 的价格卖出，收益为 $5-1=4$ ;

在第 $4$ 天以 $3$ 的价格买入，第 $5$ 天以 $6$ 的价格卖出，收益为 $6-3=3$ ，总共收益为 $4+3=7$ 。

输入描述

输入两行数字，第一行仅有一个数字，代表待股票价格的总个数，第二行是每天的股票价格 $prices$ ，股票价格之间使用空格间隔。

提示：

$1<= prices.length <= 10^5$

$0<= prices[i]<= 10^4$

输出描述

输出为一个数字，表示股票买入卖出后可获取的最大收益值。

样例1

输入

"6\n7 1 5 3 6 4"

输出

"7"