解题思路
核心思路:
这道题的关键在于理解操作的本质:每次可以选择相邻两个元素同时改变符号。我们需要找到一种策略使得最终数组元素之和最大。
让我们分析操作的影响:
- 操作将ai和ai+1都变为相反数
- 这意味着如果原来ai和ai+1都是负数,操作后变成正数,对总和有利
- 如果ai和ai+1中一个是正数一个是负数,操作可能会让总和变小
题目内容
给定一个长度为 n 的数组 {a1,a2,…,an},你可以进行以下操作若干次(可以不进行操作):
- 选择一个下标 i(1≤i<n),将 ai 与 ai+1 的符号分别翻转(即 ai←−ai,ai+1←−ai+1)。
请你计算,经过若干次操作后,数组元素之和的最大值。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤104)代表数据组数,每组测试数据描述如下:
- 第一行输入一个整数 n(1≤n≤2×105)表示数组长度;
第二行输入 n 个整数 a1,a2,…,an(−109≤ai≤109)表示数组元素。
除此之外,保证单个测试文件的 n 之和不超过 2×105。
输出描述
对于每一组测试数据,新起一行输出一个整数,表示通过若干次操作后数组元素之和的最大值。
样例1
输入
2
4
-1 -3 2 4
3
-5 2 1
输出
10
6