核心思路: 这道题的关键在于理解操作的本质:每次可以选择相邻两个元素同时改变符号。我们需要找到一种策略使得最终数组元素之和最大。
让我们分析操作的影响:
给定一个长度为 n 的数组 {a1,a2,…,an},你可以进行以下操作若干次(可以不进行操作):
请你计算,经过若干次操作后,数组元素之和的最大值。
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤104)代表数据组数,每组测试数据描述如下:
第二行输入 n 个整数 a1,a2,…,an(−109≤ai≤109)表示数组元素。
除此之外,保证单个测试文件的 n 之和不超过 2×105。
对于每一组测试数据,新起一行输出一个整数,表示通过若干次操作后数组元素之和的最大值。
输入
2
4
-1 -3 2 4
3
-5 2 1
输出
10
6
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册