CF33C Wonderful Randomized Sum

学习，学习，再学习——Valera 每天都必须这样做。他正在一所数学学校学习，数学是主要课程。数学老师非常热爱自己的学科，并努力培养孩子们对数学的热爱。因此，她总是给学生们布置大量而困难的作业。尽管 Valera 是最优秀的学生之一，这一次他还是没能完成新的作业，因此请求你的帮助。他的任务如下：给定一个长度为 $n$ 的数列。一个数列的前缀是从数列开头取出的一部分（可能为空），一个数列的后缀是从数列末尾取出的一部分（可能为空）。你可以依次对数列进行两次操作：第一次操作是取数列的某个前缀，将该前缀内的所有数都乘以 $-1$；第二次操作是取数列的某个后缀，将该后缀内的所有数都乘以 $-1$。所选的前缀和后缀可以有重叠。问经过上述操作后，数列的元素之和的最大值是多少？

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示序列的元素数量。 第二行包含 $n$ 个整数 $a_i$（$-10^4 \leq a_i \leq 10^4$），表示该数列。

输出一个整数，即经过上述操作后所能取得的数列元素和的最大值。

由 ChatGPT 5 翻译