记\(t\)为\(a\)中\(a_i<0\)的数的个数。
若\(k \le t\)，则从小到大将负数变成正数最优。
假设不这么操作最优，也就是选了一个较大的负数或者正数取反，将它们换成一个小的负数取反，答案不劣。
若\(k \ge t\)且\(k-t\)为偶数。
所有数的和为\(s_1\)，所有数的绝对值之和为\(s_2\)，\(s_1\le s_2\)恒成立。
此时将负数全部取反，剩下的次数全部用在一个数上，因为是偶数次，所以该数仍为整数，取到等号，此时答案最大。
若\(k \ge t\)且\(k-t\)为奇数。
直觉地想，肯定是将最小的那个数再翻一次。我们严格地证明这个结论。
对一个数翻转偶数次，不改变正负性；对一个数翻转奇数次，改变正负性。
我们的贪心选法分为两个步骤：
- 将\(t\)个数反转；
- 最后一次将最小的数反转。
于是，贪心解的值等于绝对值之和减去绝对值最小的数的两倍。
\(t=s_2-2m\)
如果方案最后有若干个负数\(x, y, ...\)，\(t'=s_2-2x-2y-...\le s_2-2x,x\ge m,t'\le s_2-2x\le t\)。此时贪心解最优。
如果方案最后全是正数，也就是说负数翻转了奇数次，正数翻转了偶数次，后者总操作次数一定是偶数，如果负数有奇数个，前者操作次数共奇数次，\(k\)为奇数，此时减去奇数个负数个数，应当为偶数，与剩下的\(k\)为奇数矛盾；如果负数有偶数个，前者操作次数共偶数次，\(k\)为偶数，此时减去偶数个负数个数，应当为偶数，也矛盾。
换言之，能否全部变成正数，等价于能否用1次代价操作负数之后，剩下步数为偶数。