CF2274B.Prefix
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a1,a2,…,an.
For each index i=2,3,…,n in order, perform the following:
- Define s=a1+a2+…+ai−1.
- Replace ai with one of the following three values: ai−s, ai, or ai+s.
Over all possible choices, find the maximum value of max(a1,a2,…,an) after the process described above.
给你一个数组 a1,a2,…,an。
按顺序对每个下标 i=2,3,…,n 执行以下操作:
- 定义 s=a1+a2+…+ai−1。
- 将 ai 替换为以下三个值之一:ai−s、ai 或 ai+s。
在所有可能的选择中,求上述过程结束后 max(a1,a2,…,an) 的最大可能值。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains a single integer n (2≤n≤50).
The second line of each test case contains n integers a1,a2,…,an (−50≤ai≤50).
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是测试用例的描述。
每个测试用例的第一行包含一个整数 n(2≤n≤50)。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an(−50≤ai≤50)。
输出格式
For each test case, output a single integer — the maximum achievable value of max(a1,a2,…,an).
Please note that the answer for some test cases won't fit into a 32-bit integer type, so you should use at least a 64-bit integer type in your programming language (like long long in C++).
对于每个测试用例,输出一个整数——max(a1,a2,…,an) 可达到的最大值。
请注意,某些测试用例的答案无法用 32 位整数类型表示,因此在编程语言中至少应使用 64 位整数类型(例如 C++ 中的 long long)。
输入输出样例
输入#1
4 5 3 -5 1 -4 2 2 -1 2 3 1 2 3 3 -2 -2 -2
输出#1
24 3 7 4
说明/提示
In the first test case, the final array can be made [3,−8,−4,−13,24], so the answer is 24.
In the second test case, for i=2, s=a1=−1. Replacing a2 with a2−s=2−(−1)=3 gives the answer 3.
In the third test case, the final array can be made [1,3,7], so the answer is 7.
In the fourth test case, replacing a2 with a2+s=−4 makes s=−6 for i=3. Replacing a3 with a3−s=−2−(−6)=4 gives the final array [−2,−4,4], so the answer is 4.
在第一个测试用例中,最终数组可以变为 [3,−8,−4,−13,24],因此答案为 24。
在第二个测试用例中,当 i=2 时,s=a1=−1。将 a2 替换为 a2−s=2−(−1)=3,得到答案 3。
在第三个测试用例中,最终数组可以变为 [1,3,7],因此答案为 7。
在第四个测试用例中,将 a2 替换为 a2+s=−4,使得 i=3 时 s=−6。再将 a3 替换为 a3−s=−2−(−6)=4,得到最终数组 [−2,−4,4],因此答案为 4。
输入解题思路,AI测评打分。不知道怎么写?