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吗
