在计算元素的最小和最大总和时如何通过排除列表中的一个元素来防止溢出

Question

我需要找到可以通过对数组中的 (size - 1) 个元素进行精确求和来计算的最小值和最大值

示例：
arr = [1,2,3,4,5] 最小和 = 1+2+3+4 = 10 , 最大和 = 2+3+4+5 = 14

最初，我编写了以下代码

public static void miniMaxSum(List<Integer> arr) {
    List<Integer> sorted = arr.stream().sorted().collect(Collectors.toList());
    Integer totalSum = sorted.stream().mapToInt(Integer::intValue).sum();
    Integer minSum = totalSum - sorted.get(sorted.size()-1);
    Integer maxSum = totalSum - sorted.get(0);
    System.out.println(minSum + " "+maxSum);
}

对于简单的测试用例，它按预期工作，但对于具有较高值的数字，它会溢出并导致负值，所以我使用 BigInteger。

public static void miniMaxSum(List<Integer> arr) {
    List<Integer> sorted = arr.stream().sorted().collect(Collectors.toList());
    BigInteger totalSum = BigInteger.valueOf(sorted.stream().mapToInt(Integer::intValue).sum());
    BigInteger minSum = totalSum.subtract(BigInteger.valueOf(sorted.get(sorted.size()-1)));
    BigInteger maxSum = totalSum.subtract(BigInteger.valueOf(sorted.get(0)));
    System.out.println(minSum + " "+maxSum);
}

即便如此，它也会导致负值

输入：793810624 895642170 685903712 623789054 468592370

输出：-1722871536 -1295821736

为什么使用 BigInteger 后仍会出现负值，该如何处理？

Answer 1

问题是，当您创建

totalSum

时，当您将整数求和为

int

时，就已经发生了溢出，这意味着结果也是一个

int

。只有这样，您的代码才会将此溢出结果转换为

BigInteger

。

相反，您需要使用

BigInteger

进行计算：

BigInteger totalSum = sorted.stream()
        .reduce(BigInteger.ZERO, 
                (sum, value) -> sum.add(BigInteger.valueOf(value)),
                BigInteger::add);

这相当于做：

BigInteger totalSum = sorted.stream()
        .map(v -> BigInteger.valueOf(v.longValue()))
        .reduce(BigInteger.ZERO, BigInteger::add);