4724:买卖CS饰品Ⅰ

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

总所周知,cscs 的饰品市场变幻莫测。涂涂想在接下来的 nn 天中赚上一笔,涂涂只能从 nn 天中的第 ii 天把饰品买入,并在第 jj 天卖出(i<ji \lt j)。现在,他想知道他能从中获得的最高利润是多少?

输入描述

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

每组案例的第一行是一个正整数 nnnn 如题意所示。(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​)

输出描述

对于每组案例,输出一行表示能获取的最大利润,如果不能获取任何利润则输出 00

样例输入复制样例

1

6

7 1 5 3 6 4

样例输出

5

提示说明

只能买卖一次

相关

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


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