C1. Magnitude (Easy Version) 详细题解

题目重述

给定一个长度为 $n$ 的数组 $a$，初始 $c=0$。按顺序处理每个元素 $a_i$，每次可以选择：

• 令 $c \leftarrow c + a_i$，或
• 令 $c \leftarrow |c + a_i|$。

求最终 $c$ 的最大可能值。

核心观察

绝对值操作可以在任何时刻进行。一旦取绝对值，$c$ 变为非负数，后续操作在此基础上继续。直觉上，我们只关心在什么时候“翻转”符号。事实上，可以证明：最优策略中，至多取一次绝对值。因为如果两次取绝对值，中间必然会有一次正负变化，而我们可以合并为一次。

考虑前缀和 $S_i = \sum_{j=1}^i a_j$（$S_0 = 0$）。假设我们在处理完第 $p$ 个元素后（即 $c = S_p$）取绝对值，则 $c$ 变为 $|S_p|$，然后继续加上剩余元素（不再取绝对值，因为后续再取可以合并到这次）。最终结果为：

$$|S_p| + (S_n - S_p) = S_n + (|S_p| - S_p).$$

因此，我们需要最大化这个值，其中 $p$ 可以取 $0,1,\dots,n$（$p=0$ 表示从不取绝对值，结果为 $S_n$）。

而 $|S_p| - S_p = \begin{cases} 0, & S_p \ge 0 \\ -2S_p, & S_p < 0 \end{cases}$。所以最大值等于：

$$S_n + \max_{0\le p\le n}(|S_p| - S_p) = S_n + \max(0,\; -2\min_{p} S_p) = S_n - 2\cdot\min(0,\; \min_{p} S_p). $$

记 $m = \min_{0\le p\le n} S_p$，则答案为：

$$k = S_n - 2 \cdot \min(0, m).$$

算法步骤

1. 计算全部元素的和 $total = \sum_{i=1}^n a_i$。
2. 遍历数组，计算前缀和 $cur$，并记录最小前缀和 $min\_pref$（包括 $cur=0$ 的初始状态）。
3. 答案 $= total - 2 \cdot \min(0, min\_pref)$。
4. 输出答案（注意使用 64 位整数）。

正确性证明

• 任何操作序列可以转化为：存在某个分界点 $p$，使得前 $p$ 个元素正常加（不取绝对值），然后第 $p$ 步后取一次绝对值，后续元素直接加（不再取绝对值）。因为若在多个位置取绝对值，可以合并：假设在 $p$ 和 $q$（$p<q$）取绝对值，则 $c$ 的变化为 $S_p \to |S_p| \to \cdots$，但后续操作等价于在 $p$ 处一次取绝对值后，将后面部分视为整体。形式化证明可参考贪心：绝对值操作相当于符号翻转，多次翻转等价于一次。
• 因此所有可能结果形如 $|S_p| + (S_n - S_p)$。最大值即为上述表达式。
• 由于 $|S_p| - S_p$ 在 $S_p \ge 0$ 时为 $0$，否则为 $-2S_p$，所以最大值对应 $\min S_p$（若为负）或 $0$。
• 当所有前缀和 $\ge 0$ 时，$m \ge 0$，答案为 $S_n$；否则答案为 $S_n - 2m$。

复杂度

• 每个测试用例 $O(n)$ 时间，$O(1)$ 额外空间。
• 所有测试用例的 $n$ 总和 $\le 3\times 10^5$，完全可行。

示例验证

• 例1：$a=[10,-9,-3,4]$，$S=[10,1,-2,2]$，$m=-2$，$total=2$，$ans=2-2\cdot(-2)=6$。
• 例2：全正，$m\ge0$，$ans=24$。
• 例3：全负，$m=-6$，$total=-6$，$ans=-6-2\cdot(-6)=6$。
• 例4：$a=[-10^9,10^9,10^9,10^9]$，$S=[-10^9,0,10^9,2\cdot10^9]$，$m=-10^9$，$total=2\cdot10^9$，$ans=2\cdot10^9+2\cdot10^9=4\cdot10^9$。
• 例5：全正，$ans=22$。

均与样例输出一致。

总结

本题的关键在于发现只需考虑一次绝对值操作，并转化为前缀和的最小值。通过简单扫描即可求得答案，避免了复杂的 DP。这是 Codeforces 上典型的贪心/数学题，适合快速解决。