Responsive image

问题 3116 --数学奇才

3116: 数学奇才

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 29
[提交][状态][讨论版][命题人:]

题目描述

你是一位数学奇才，但却被困在了神秘的数字王国中。在你面前，摆放着一串神奇的数字，它们组成了一个长度为 n 的序列，记作 a。你的使命是利用你特殊的能力，最大化序列中所有数字的总和，但是有一个限制：你只能进行不超过 n 次操作。
那么，你的特殊能力是什么呢？嗯，你可以选择序列中的某一段连续的数字，然后将它们变为自身的相反数。举个例子，假设你选择了位置 i，那么 a1,a2,…,ai中的每个数字都会乘以 −1。
现在，你需要巧妙运用你的能力，设计一种操作方案，使得经过不超过n次操作后，序列a中所有数字的总和尽可能大。请计算出这个最大的总和是多少？！

输入描述

第一行包含一个整数 n，表示序列 a 的长度 (1≤n≤105)。
第二行包含 n 个整数 a1,a2,…,an表示序列 a 中的元素 (−109≤ai≤109)。

输出描述

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

样例输入

3
-1 -2 3

样例输出

6

来源

 

[提交][状态]
ACM算法攻关部