覆盖 0 次
没有被前缀或后缀选中，元素保持原来的符号。
2026 / 07
03
星期五
TODAY'S RESEARCH · Codeforces 33C
从两次翻转，
走到最大子段和
今天开始研究 Wonderful Randomized Sum。先不背结论，而是从每个元素究竟被翻转几次开始推导。
正在研究
关键转化已经独立推出
两边翻转、中间不变 → 选择一个和最大的连续中间段。
下一步
独立实现并测试
还没有把推导完整写成自己的 AC 代码。
PROBLEM · 题目
CODEFORCES 33C
Wonderful Randomized Sum
给定一个整数序列。可以选择一个前缀乘以 −1，再选择一个后缀乘以 −1；前后缀都可以为空，也可以相交。求操作后最大的序列总和。
在洛谷查看原题OBSERVATION · 自己观察到的规律
先数“翻转次数”，再看最终结构
同一个元素只可能被覆盖 0 次、1 次或 2 次。
覆盖 1 次
只属于前缀或只属于后缀，乘一次 −1，符号翻转。
覆盖 2 次
(−1) × (−1) = 1，前后缀重叠部分最终不变。
最终只有三段
无论前后缀是否相交，都可写成：左边翻转｜中间不变｜右边翻转。
TRANSFORM · 代数转化
把操作题，变成一个熟悉的问题。
设原数组总和为 S，中间不变区间的元素和为 M。两侧元素之和就是 S − M，它们都会被取反。
最终总和
M − (S − M) = 2M − S S 是固定的，因此只需让 M 尽可能大。 问题转化为：求最大子段和。
01
KADANE · 实现方向
一边扫描，一边保留最有价值的连续段
- 累计总和
用
sum记录整个数组的元素和 S。 - 维护当前段
current = max(0LL, current + x)。如果当前连续和已经为负，就从后面重新开始。 - 维护最优段
best = max(best, current)，得到允许为空的最大子段和 M。 - 计算答案
最终输出
2 * best - sum。
CHECKPOINT · 当前进度
已经真正想明白的
- 两次翻转会相消，重叠部分不变。
- 最终符号结构可以统一表示为“两头翻转，中间不变”。
- 最终和可以写成 2M − S。
- 最大化 M 就是求最大子段和。
NEXT · 接下来完成
还没有打勾的
- 不看模板，独立写出 Kadane。
- 手算全负数、全正数和正负混合三类样例。
- 解释为什么中间段允许为空或为整个数组。
- 提交并记录第一次错误与修正。