求可转为负数的最大数量：数组累积和恒正的算法问题

给定一个长度为n的正整数数组，需要选择尽可能多的元素将其乘以-1，确保每一步的累积和始终大于0，返回可转为负数的元素最大数量。

示例 #

• 测试用例1：[5,3,1,2]
• 结果：2
• 解释：选择索引1和2的元素转为负数，得到[5,-3,-1,2]，累积和为[5,2,1,3]；也可选择[5,-3,1,-2]等方案。

错误实现 #

用户最初的代码实现如下，该代码在处理测试用例[5,2,3,5,2,3]时返回2，但预期输出为3（可行方案：[5,-2,3,5,-2,-3]）：

static int solve(int[] arr) {
    long sum = 0;
    int result = 0;
    for(int e : arr) {
        int neg = -e;
        if(sum + neg >0) {
            result++;
            sum += neg;
        } else {
            sum += e;
        }
    }
    return result;
} 

正确解决思路 #

错误代码的问题在于贪心策略过于短视：只看当前元素转负后是否满足累积和>0，没有考虑后续可以通过调整已转负的元素来容纳更多负数。正确的贪心策略需要结合最小堆（优先队列）来优化：

1. 遍历数组时，先尝试将当前元素转为负数，加入累积和，并将该元素的绝对值存入最小堆，同时计数加1。
2. 如果此时累积和<=0，说明当前转负的操作导致违反规则，需要撤销之前转负的最小元素（因为最小的元素转负后对累积和的负面影响最小，撤销它能让累积和回升最多）：从堆中取出最小元素，将累积和加上该元素的2倍（相当于把-elem变回elem，即sum = sum - (-elem) + elem = sum + 2*elem），同时计数减1。
3. 遍历结束后，计数就是可转为负数的最大数量。

代码实现示例 #

import java.util.PriorityQueue;

static int solve(int[] arr) {
    long sum = 0;
    int count = 0;
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : arr) {
        sum -= num;
        minHeap.offer(num);
        count++;
        
        // 如果累积和不满足条件，撤销最小的负元素
        while (sum <= 0) {
            int smallest = minHeap.poll();
            sum += 2 * smallest;
            count--;
        }
    }
    return count;
}

思路解释 #

• 优先转负所有元素，当出现累积和违规时，撤销对累积和影响最小的那个负元素（也就是原数组中最小的元素），这样能最大化保留更多的负元素。
• 最小堆的作用是快速获取已转负元素中的最小值，保证每次撤销的都是最优选择，从而让整体能容纳最多的负元素。

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