解题思路

• 本题要求在“最多持有一股、可多次交易（同一天可买或卖但不能同时持有多股）”的条件下，使收益最大。

• 相关算法：贪心 / 动态规划（两种说法等价）。

  • 贪心核心：只要今天价格比昨天高，就把这段上涨的差价计入收益，即累加所有相邻两天的正向差值 max(0, price[i] - price[i-1])。这样等价于在每一段上升区间“谷底买、峰顶卖”的效果。
  • 等价的 DP 表达（可作为思路背书）： 设 hold 为持有一股时的最大现金，cash 为不持有时的最大现金。 迭代转移：

题目内容

给定一个正整数（表示股票价格列表的总个数）和一个非负整数列表（表示股票每天的价格）。用户初始不持有股票，要求每天仅能持有一份股票，且每天可以买入或卖出股票。计算通过买入卖出股票能获得的最大现金收益，若无法取得收益则返回 $0$ 。

输入描述

第一行输入一个整数 $n$ ，表示股票价格列表的总个数

第二行输入一个非负整数列表，表示股票每天的价格

输出描述

输出能获得的最大现金收益

样例1

输入

6
7 1 5 4 6 4

输出

6