算法
(贪心) $O(n)$
注意到,对于 $i=x,x+1, \cdots,y-1$ 这些数执行该操作,最后只有 $A_x$ 和 $A_y$ 改变了符号。通过该操作,$A_i$ 会变成它的相反数。特别地,对于 $A_i = 0$ 而言,执行该操作对 $A_i$ 不会有影响。于是可以得到有偶数个负数或者存在 $A_i = 0$ 时,我们可以通过该操作把所有数变成非负数,否则经过该操作将会存在一个负数,此时我们不妨把 $min|A_i|$ 设为需要去掉的负数即可。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::min;
using ll = long long;
const int INF = 1001001001;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
ll ans = 0;
int neg = 0;
for (int i = 0; i < n; ++i) {
ans += abs(a[i]);
if (a[i] < 0) neg++;
}
if (neg % 2 == 1) {
int minA = INF;
for (int i = 0; i < n; ++i) minA = min(minA, abs(a[i]));
ans -= minA * 2;
}
cout << ans << '\n';
return 0;
}