4729:买卖CS饰品Ⅵ

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

总所周知,cscs 的饰品市场变幻莫测。涂涂想在接下来的 nn 天中赚上一笔,涂涂在每一天中,可以决定是否购买 和/或 出售饰品。涂涂在任何时候 最多 只能持有 一件 饰品。涂涂也可以先购买,然后在 同一天 出售。

当涂涂卖出饰品后,无法在第二天购入饰品(即存在一天的交易冷却期)。

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

输入描述

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

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

每组案例的第二行包含 nn 个整数:a1,a2,...,ana_1,a_2,...,a_n 表示每天的饰品价格。(0ai1090\le a_i\le 10^9

输出描述

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

样例输入复制样例

2

5

1 2 3 0 2

1

1

样例输出

3

0

相关

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


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