使前缀和非负所需的最少符号翻转次数问题

问题背景 #

给定长度为n的整数列表，需找到最少的元素符号翻转次数，使得列表的所有前缀和（前k个元素的和，1≤k≤n）均非负。

你提出的贪心算法流程：

• 从列表头部开始遍历；
• 维护当前前缀和与已翻转元素计数f；
• 遍历到第k+1个元素时，若加入后前缀和非负，继续；
• 若前缀和为负，翻转0~k+1范围内最负的元素，f加1。

针对你疑问的解答 #

为什么仅新增一次翻转是最优的？ #

我们的核心目标是最小化翻转次数，所以每一步都要尽可能少增加翻转次数。当当前前缀和为负时，必须至少新增一次翻转——不翻转的话前缀和直接违反要求，而新增1次是满足当前条件的最小增量。

至于“取消之前m次翻转再翻转m+1次”的思路，完全不可行：之前的所有翻转都是保证前面所有前缀和非负的必要操作，一旦取消任意一次之前的翻转，对应的前面的前缀和就会变成负的，直接违反题目约束。因此之前的翻转不能撤销，只能在现有基础上新增翻转，而新增1次是最优选择。

为什么选当前范围内最负的元素翻转？ #

翻转元素的目的是让当前前缀和尽可能大，给后续遍历留出足够的“缓冲空间”，减少后续触发翻转的次数。

对于当前范围内的负数元素，越负的元素翻转后带来的前缀和提升越大：假设元素为x（x<0），翻转后前缀和会增加2*|x|，x的绝对值越大，增量就越大。选择翻转最负的元素，能让当前前缀和达到最大可能值，后续加入新元素时更不容易出现前缀和为负的情况，从而保证总翻转次数最少。

贪心策略的最优性证明 #

假设存在一个最优方案，总翻转次数比贪心方案少：

1. 若该方案在某一步没有翻转元素，那当前前缀和为负，违反约束，不可能是合法方案；
2. 若该方案翻转了非最负的元素，当前前缀和的增量比贪心方案小，后续遇到元素时更容易触发翻转，总次数会超过贪心方案，与“最优”矛盾。

因此，贪心策略能得到最少的翻转次数。

内容的提问来源于stack exchange，提问作者Marc Carlsan