3.蛋滚派对
题目描述
“趴着好难受啊蛋！我要透不过气了蛋！”
“我也不想仰着睡啊蛋！！！”
“那咱俩都翻过来睡呗蛋！”
n 个蛋蛋排成一排睡觉，有些蛋蛋喜欢趴着睡，有些则喜欢仰着睡。你可以做任意次操作，使得相邻的两个蛋蛋都翻过来睡。它们最开始都有个愉悦值，对于任何一个蛋蛋，翻过来之后愉悦值都会变成原来的相反数。
请你最大化它们的愉悦值之和，并回答这个值。
注意：第 1 个蛋蛋和第 n 个蛋蛋不相邻！
输入格式
第一行一个正整数 n ，表示蛋蛋的数量。
第二行 n 个整数，其中第 i 个整数 a_i 表示第 i 个蛋蛋的初始愉悦值。
输出格式
一个整数，表示操作后的最大愉悦值之和。
样例
Input 1
3
-10 5 -4
Output 1
19
Input 2
5
10 -4 -8 -11 3
Output 2
30
Input 3
11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000
Output 3
10000000000
样例解释
样例一中， 1,2 翻滚， 2,3 翻滚，最后愉悦值为 \{10,5,4\} ，总和为 19 。
样例二中， 2,3 翻滚， 4,5 翻滚，最后愉悦值为 \{10,4,8,11,−3\} ，总和为 30 。
数据范围
- 对于数据 1∼4 ： 1≤n≤4000
- 对于数据 5∼20 ： 1≤n≤10^5
- 对于所有数据： −10^9≤a_i≤10^9
【分析】
n 的范围已经到 10^5 ，两重循环就会 TLE ，光看题面是不行的，我们需要在它的样例里找规律。
他说可以翻相邻两个蛋使他们的愉悦值变成相反数，可以得出不管怎么翻翻的个数总是偶数，只要知道这个就好办了，见规律。
规律如下：
\begin{array}{l}
\left\{\begin{matrix}
负数个数为奇数 \text{则ans=所有项绝对值的和减去2*绝对值最小的那个数的绝对值} \\ 负数个数为偶数 \text{则ans=所有项绝对值的和} \end{matrix}\right. \end{array}
只要有了规律接下来就很简单了，代码请自行实现。 