4726:买卖CS饰品Ⅲ

时间限制:2 S   /  内存限制:65536 KB
AC:13   /  Submit:17
问题描述

总所周知,$$cs$$ 的饰品市场变幻莫测。涂涂想在接下来的 $$n$$ 天中赚上一笔,涂涂在每一天中,可以决定是否购买 和/或 出售饰品。涂涂在任何时候 最多 只能持有 一件 饰品。涂涂也可以先购买,然后在 同一天 出售。由于涂涂被限额,所以他最多只能完成 两笔 交易。

现在,他想知道他能从中获得的最大利润是多少?

输入描述

这是一道多组案例的题目。一个正整数 T,表示案例的数量。($$1\le T \le 10$$)

每组案例的第一行是一个正整数 $$n$$,$$n$$ 如题意所示。($$1\le n \le 1 \times 10^5$$)

每组案例的第二行包含 $$n$$ 个整数:$$a_1,a_2,...,a_n$$ 表示每天的饰品价格。($$0\le a_i\le 10^9$$)

输出描述

对于每组案例,输出一行表示能获取的最大利润。

样例输入复制样例

2

8

3 3 5 0 0 3 1 4

5

1 2 3 4 5

样例输出

6

4

相关

题单#20(动态规划之状态机模型)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1