JavaScript算法问题:从一个数组中找到和最大的邻接子数组

找到和最大的邻接子数组（也称为最大子数组和问题）是一个经典的算法问题，通常使用 Kadane's Algorithm 来解决。这个算法的时间复杂度是 O(n)，非常高效。

以下是 Kadane's Algorithm 的实现步骤：

1. 初始化两个变量：maxSoFar 和 maxEndingHere，都设置为数组的第一个元素。
2. 遍历数组，从第二个元素开始。
3. 对于每个元素，更新 maxEndingHere 为当前元素和 maxEndingHere + 当前元素 中的较大值。
4. 更新 maxSoFar 为 maxSoFar 和 maxEndingHere 中的较大值。
5. 最后，maxSoFar 就是和最大的邻接子数组的和。

JavaScript 实现

function maxSubArray(nums) {
    if (nums.length === 0) return 0;

    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];

    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

// 示例
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // 输出: 6

解释

1. 初始化：
   • maxSoFar 和 maxEndingHere 都初始化为数组的第一个元素。
2. 遍历数组：
   • 从数组的第二个元素开始遍历。
   • 对于每个元素，计算 maxEndingHere，它是当前元素和 maxEndingHere + 当前元素 中的较大值。这一步决定了是否将当前元素加入到之前的子数组中，还是从当前元素重新开始一个新的子数组。
   • 更新 maxSoFar，它是 maxSoFar 和 maxEndingHere 中的较大值。这一步记录了迄今为止找到的最大子数组和。
3. 返回结果：
   • 最后，maxSoFar 就是和最大的邻接子数组的和。

示例解释

对于数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]：

• 初始化：maxSoFar = -2, maxEndingHere = -2
• 第一步：maxEndingHere = max(1, -2 + 1) = 1, maxSoFar = max(-2, 1) = 1
• 第二步：maxEndingHere = max(-3, 1 - 3) = -2, maxSoFar = max(1, -2) = 1
• 第三步：maxEndingHere = max(4, -2 + 4) = 4, maxSoFar = max(1, 4) = 4
• 第四步：maxEndingHere = max(-1, 4 - 1) = 3, maxSoFar = max(4, 3) = 4
• 第五步：maxEndingHere = max(2, 3 + 2) = 5, maxSoFar = max(4, 5) = 5
• 第六步：maxEndingHere = max(1, 5 + 1) = 6, maxSoFar = max(5, 6) = 6
• 第七步：maxEndingHere = max(-5, 6 - 5) = 1, maxSoFar = max(6, 1) = 6
• 第八步：maxEndingHere = max(4, 1 + 4) = 5, maxSoFar = max(6, 5) = 6

最终结果是 6，对应的子数组是 [4, -1, 2, 1]。