题目描述

难度分:$833$

输入$n(2 \leq n \leq 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

你可以执行如下操作任意多次：

• 选择$a$中两个相邻数字，把它们俩都乘上$-1$。

输出$sum(a)$的最大值。

输入样例$1$

3
-10 5 -4

输出样例$1$

19

输入样例$2$

5
10 -4 -8 -11 3

输出样例$2$

30

输入样例$3$

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

输出样例$3$

10000000000

算法

贪心

这个题手玩一下用例可以发现，如果有奇数个负数，因为每次操作能改变两个数的符号，最后必然会有一个数是负号，此时让绝对值最小的那个数是负号即可。其他情况都能将所有元素变成非负数（如果有$0$，只需要把负号给$0$即可，$0$的相反数还是自己，没什么损失），答案就是数组中所有元素的绝对值之和。

复杂度分析

时间复杂度

整个算法遍历了一遍数组，求得所有元素的绝对值之和以及绝对值最小值，时间复杂度为$O(n)$。

空间复杂度

仅使用有限几个变量就能统计出数组$a$中是否有$0$，以及负数的个数，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, a[N];

int main() {
    scanf("%d", &n);
    int cnt[3] = {0};
    int e = 1e9 + 1;
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(a[i] == 0) {
            cnt[0]++;
        }else if(a[i] > 0) {
            cnt[1]++;
        }else {
            cnt[2]++;
        }
        ans += abs(a[i]);
        e = min(e, abs(a[i]));
    }
    if(cnt[0] > 0) {
        printf("%lld\n", ans);
        exit(0);
    }
    if(cnt[2]&1) ans -= e<<1;
    printf("%lld\n", ans);
    return 0;
}