Java 找到允许的最大底片

发布于04月09日

给定一个大小为n的正数数组，从这个数组中挑选尽可能多的项目并乘以—1，这样累积和总是大于0.返回多少项可以作为结果变成负数.

Example:

测试 case 1:[5，3，1，2]

结果= 2

Explanation:

Select 指数1和2并使它们为负值所以[5，—3，—1，2] 累计总和为[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]

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

推荐答案

如果可能的话，您总是可以try 求反当前元素，同时保持跟踪多集或优先级队列中迄今为止移除的元素.如果当前元素不能从总和中删除，则try 将其替换为先前删除的最大元素(如果后者更大).

static int solve(int[] arr) {
    long sum = 0;
    int result = 0;
    var removed = new PriorityQueue<Integer>(Collections.reverseOrder());
    for (int x : arr) {
        if (sum - x > 0) {
            sum -= x;
            removed.add(x);
            ++result;
        } else if (!removed.isEmpty() && removed.peek() > x) {
            sum += removed.poll() - x;
            removed.add(x);
        } else sum += x;
    }
    return result;
}