题目描述

给定一个整数数组 $prices$，其中 $prices[i]$ 表示某支股票第 $i$ 天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行一个整数 $n$ 表示数组的长度；

第二行 $n$ 个整数表示数组中的每个元素。

输出格式

一行一个整数表示答案。

示例 1:

5
1 2 3 0 2

3

解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

示例 2:

1
1

0

提示:

• $1 <= prices.length <= 5000$
• $0 <= prices[i] <= 1000$