C++实现miniMaxSum四元素最值求和逻辑错误排查

需求为计算入参传入的5元素vector中，选取4个元素求和得到的最小值与最大值。编写的C++实现代码仅能通过15个测试用例中的5个，需要排查代码问题。

未通过的测试用例输入 #

• 测试用例1：254961783 604179258 462517083 967304281 860273491
• 测试用例2：793810624 895642170 685903712 623789054 468592370
• 测试用例3：140537896 243908675 670291834 923018467 520718469

问题根因 #

代码存在32位整数溢出问题：

1. 入参vector<int> arr的元素是32位int类型，单类型最大值约为21.47亿。
2. 计算sum1-sum5时，等号右侧是4个int值直接相加，运算过程中所有值默认按int类型计算，4个接近10亿的数相加结果超过32位int的上限，触发有符号整数溢出（属于未定义行为），此时计算结果已经错误。
3. 虽然sum1-sum5定义为long int类型，但错误的int运算结果在赋值前就已经溢出，后续转换为long类型也无法得到正确值。

原有问题代码 #

void miniMaxSum(vector<int> arr) {
    long int sum1, sum2, sum3, sum4, sum5;
    long int min = INT_MAX ;
    long int max = INT_MIN;
    sum1 = arr[0] + arr[1] + arr[2] + arr[3];
    sum2 = arr[1] + arr[2] + arr[3] + arr[4];
    sum3 = arr[0] + arr[4] + arr[2] + arr[3];
    sum4 = arr[0] + arr[1] + arr[4] + arr[3];
    sum5 = arr[0] + arr[1] + arr[2] + arr[4];
    
    long int sum[5] = {sum1, sum2, sum3, sum4, sum5};
    
    for (int i = 0; i < 5; i++) {
        if (sum[i] > max)
            max = sum[i];
      
        if (sum[i] < min)
            min = sum[i];
    }

    cout << min << " " << max;
}

修复方案 #

核心修复逻辑：相加前先将单个元素转为long类型，让整个加法运算在64位整数空间下计算，从根源避免int阶段溢出。

void miniMaxSum(vector<int> arr) {
    long int sum1, sum2, sum3, sum4, sum5;
    long int min = LONG_MAX;
    long int max = LONG_MIN;
    // 第一个元素强转为long，后续运算自动提升为long类型，避免溢出
    sum1 = (long)arr[0] + arr[1] + arr[2] + arr[3];
    sum2 = (long)arr[1] + arr[2] + arr[3] + arr[4];
    sum3 = (long)arr[0] + arr[4] + arr[2] + arr[3];
    sum4 = (long)arr[0] + arr[1] + arr[4] + arr[3];
    sum5 = (long)arr[0] + arr[1] + arr[2] + arr[4];
    
    long int sum[5] = {sum1, sum2, sum3, sum4, sum5};
    
    for (int i = 0; i < 5; i++) {
        if (sum[i] > max)
            max = sum[i];
      
        if (sum[i] < min)
            min = sum[i];
    }

    cout << min << " " << max;
}

更简洁的实现思路：先计算5个元素的总和，再分别减去每个元素得到5组4元素求和结果，无需手动枚举所有组合，代码容错率更高：

void miniMaxSum(vector<int> arr) {
    long total = 0;
    for (int num : arr) total += num;
    long minSum = LONG_MAX, maxSum = LONG_MIN;
    for (int num : arr) {
        long current = total - num;
        minSum = min(minSum, current);
        maxSum = max(maxSum, current);
    }
    cout << minSum << " " << maxSum;
}

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