提高-⏱ 1000ms💾 256MB#P7013

题目描述

股票交易:每天可买入一股(持有多股时不可再买)、卖出持有的一股,或不操作。卖出后的次日不能买入(冷冻期)。求 $n$ 天结束时的最大利润。初始无持股。

输入格式

第一行整数 $n$;第二行 $n$ 个正整数价格。

输出格式

一行一个整数,即最大利润。

数据范围

$$1 \le n \le 5000,\ 1 \le p_i \le 10^4$$

样例输入 #1
1
7
样例输出 #1
0
样例输入 #2
2
1 2
样例输出 #2
1