找到允许的最大负数

Question

给定一个大小为 n 的正数数组，从该数组中选取尽可能多的项并乘以 -1，使得累积和始终大于 0。返回结果中有多少项可以为负数。

示例：

Test case1 : [5,3,1,2]

Result = 2

说明：

pick indices 1 and 2 and make them negative
so [5,-3,-1,2]
cumulative sum is [5,2,1,3]

还有其他可能性，比如

[5,-3,1,-2]

我的编码方法是这样的：

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;
} 

但是我的方法不正确，因为它在某些情况下给出错误的输出，例如：

arr = [5,2,3,5,2,3]

Expected output = 3, my code results = 2

possible solution is [5,-2,3,5,-2,-3]

解决这个问题的正确方法是什么？

Answer 1

您的方法永远不会包含第一个元素（因为要使其为负），因为循环的第一次迭代将始终进入

else

块。您甚至可以设计一个输入，您的函数永远不会进入

if

块，因此将返回 0:

{1,2,4,8,16,32,64,128}

解决这个问题的关键是对数组进行排序。如果不允许更改输入数组，则复制并排序 that 数组。

然后按排序顺序取值，直到它们的总和不再小于总和的一半。返回这些的数量。

    static int solve(int[] arr) {
        Arrays.sort(arr);

        // Get half of the sum, rounded up (hence starting with 1) 
        long sum = 1;
        for (int val : arr) sum += val;
        sum /= 2;

        // As long as a running sum in sorted order 
        //    stays below this limit, keep counting
        int count = 0;
        for (int val : arr) {
            sum -= val;
            if (sum <= 0) break;
            count++;
        }
        return count; 
    }