分治法求解最大子数组时JavaScript变量意外变更问题

问题现象 #

输入数组 nums=[-2,1,-3,4,-1,2,1,-5,4] 时，某分治法实现返回结果为4，与预期的6不符；但将中间子数组和存入变量后再传入Math.max()，代码即可返回正确结果。

错误实现代码 #

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    function mergeSort(all, left, right) {
        if ( left > right ) {
            return Number.NEGATIVE_INFINITY;
        }
        const mid = Math.floor((left + right) / 2);
        let leftSum = rightSum = currentSum = 0;
        // 计算左侧最大后缀和
        for (i = mid - 1; i >= left; i -= 1) {
            currentSum = currentSum + all[i];
            leftSum = Math.max(leftSum, currentSum);
        }
        currentSum = 0;
        // 计算右侧最大前缀和
        for (i = mid + 1; i <= right; i += 1) {
            currentSum = currentSum + all[i];
            rightSum = Math.max(rightSum, currentSum);
        }
        // 比较左子数组、右子数组、跨中点子数组的最大和
        const result = Math.max(mergeSort(all, left, mid - 1), 
                                mergeSort(all, mid + 1, right), 
                                leftSum + all[mid] + rightSum);
        return result
    }
    return mergeSort(nums, 0, nums.length - 1);
};

const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums)); // 4 ???

修正后正确代码 #

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    function mergeSort(all, left, right) {
        if ( left > right ) {
            return Number.NEGATIVE_INFINITY;
        }
        const mid = Math.floor((left + right) / 2);
        let leftSum = rightSum = currentSum = 0;
        // 计算左侧最大后缀和
        for (i = mid - 1; i >= left; i -= 1) {
            currentSum = currentSum + all[i];
            leftSum = Math.max(leftSum, currentSum);
        }
        currentSum = 0;
        // 计算右侧最大前缀和
        for (i = mid + 1; i <= right; i += 1) {
            currentSum = currentSum + all[i];
            rightSum = Math.max(rightSum, currentSum);
        }
        // 先计算跨中点子数组和并保存
        const middlePart = leftSum + all[mid] + rightSum;
        // 比较三个候选值
        const result = Math.max(mergeSort(all, left, mid - 1), 
                                mergeSort(all, mid + 1, right), 
                                middlePart);
        return result
    }
    return mergeSort(nums, 0, nums.length - 1);
};

const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums)); // 6 (good!)

核心原因分析 #

问题根源是循环变量i未声明，导致其成为全局变量：

1. 在错误实现中，Math.max()的参数会从左到右依次计算：先执行两次递归调用mergeSort，递归过程中会再次使用全局的i进行循环，直接修改了i的全局值。
2. 当最后计算leftSum + all[mid] + rightSum时，之前的循环已经因为i被递归中的循环篡改，导致leftSum或rightSum的计算逻辑被破坏，得到错误的中间和。
3. 修正后的代码先计算并保存middlePart，此时i还未被递归修改，中间和的计算是正确的；后续递归即使修改全局i，也不会影响已经保存的middlePart。

更彻底的解决方法是给循环变量i添加块级作用域声明（let i），避免全局变量污染：

// 修改循环部分
for (let i = mid - 1; i >= left; i -= 1) {
    currentSum = currentSum + all[i];
    leftSum = Math.max(leftSum, currentSum);
}
for (let i = mid + 1; i <= right; i += 1) {
    currentSum = currentSum + all[i];
    rightSum = Math.max(rightSum, currentSum);
}

此时每个循环的i都是独立的块级变量，递归调用不会互相干扰，即使不提前保存middlePart，代码也能正常运行。

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