20 数学奇才

【难度: 简单，标签: 贪心，通过率: 71.6%】

20.1 问题描述

你是一位数学奇才，但却被困在了神秘的数字王国中。在你面前，摆放着一串神奇的数字，它们组成了一个长度为 n 的序列，记作 a。你的使命是利用你特殊的能力，最大化序列中所有数字的总和，但是有一个限制：你只能进行不超过 n 次操作^{20}。

那么，你的特殊能力是什么呢？嗯，你可以选择序列中的某一段连续的数字，然后将它们变为自身的相反数。举个例子，假设你选择了位置 i，那么 a_1,a_2,\dots,a_i 中的每个数字都会乘以 -1。

^{20}参见https://www.lanqiao.cn/problems/16991/learning/?page=5&first_category_id=1&second_category_id=15

现在，你需要巧妙运用你的能力，设计一种操作方案，使得经过不超过 n 次操作后，序列 a 中所有数字的总和尽可能大。请计算出这个最大的总和是多少？！

20.2 输入格式

第一行包含一个整数 n，表示序列 a 的长度 (1 \le n \le 10^5)。

第二行包含 n 个整数 a_1,a_2,\dots,a_n，表示序列 a 中的元素 (-10^9 \le a_i \le 10^9)。

20.3 输出格式

输出一个整数，表示经过不超过 n 次操作后，序列 a 中所有数字的最大总和。

20.4 样例输入

plaintext

3

-1 -2 3

20.5 样例输出

plaintext

6

20.6 样例说明

一种最优的操作方案是：选择位置2，将序列变为 [1,2,3]。这样一来，序列中所有数字的总和为 1+2+3=6，显然，不会有比这更大的数字总和了。

20.7 评测数据规模

对于所有测评数据，1 \le n \le 10^5，-10^9 \le a_i \le 10^9。

#include <stdio.h>

#include <stdlib.h>

long long maxsum(int n, int a[]) {

for (int i = n - 1; i >= 0; i--) {

if (a[i] < 0) {

for (int j = 0; j <= i; j++) {

a[j] = -a[j];

}

}

}

long long sum = 0;

for (int i = 0; i < n; i++) {

sum += a[i];

}

return sum;

}

int main() {

int n;

scanf("%d", &n);

int *a = (int *)malloc(n * sizeof(int));

for (int i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

long long ans = maxsum(n, a);

printf("%lld\n", ans);

free(a);

return 0;

}这个代码对吗？能保证操作次数不超过n吗