Maximum Subarray（最大子数组和）

题目 / Problem

中文： 给定一个整数数组 nums，找出和最大的连续子数组，并返回该子数组的元素总和。

子数组必须是原数组中连续的一段，并且至少包含一个元素。
A subarray must be a contiguous, non-empty part of the original array.

English: Given an integer array nums, find the subarray with the largest sum and return its sum.

示例 / Examples

Example 1

Input:  nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

解释 / Explanation:
连续子数组 [4,-1,2,1] 的和最大，为 6。
The contiguous subarray [4,-1,2,1] has the largest sum, which is 6.

Example 2

Input:  nums = [1]
Output: 1

解释 / Explanation:
唯一的非空子数组是 [1]，所以最大和为 1。
The only non-empty subarray is [1], so the maximum sum is 1.

Example 3

Input:  nums = [5,4,-1,7,8]
Output: 23

解释 / Explanation:
整个数组 [5,4,-1,7,8] 的和最大，为 23。
The entire array [5,4,-1,7,8] has the largest sum, which is 23.

约束 / Constraints

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴

进阶 / Follow-up

在实现 O(n) 解法后，尝试使用更巧妙的分治方法解决此问题。
After implementing the O(n) solution, try solving the problem with the more subtle divide-and-conquer approach.

解题思路一：Kadane 算法 / Approach 1: Kadane's Algorithm

遍历到 nums[i] 时，只需决定一件事：以当前元素结尾的最大子数组应该：
At nums[i], make one decision: should the maximum subarray ending at the current element:

1. 接在前一个位置的最大连续和后面；或者
   Extend the maximum subarray ending at the previous position; or
2. 放弃之前的部分，从当前元素重新开始。
   Discard the previous portion and start again at the current element.

因此状态转移为：
The state transition is:

currentSum = max(nums[i], currentSum + nums[i])

其中：
Where:

• currentSum 表示必须以当前位置结尾的最大子数组和。
  currentSum is the maximum sum of a subarray that must end at the current position.
• maxSum 表示目前为止所有子数组中的最大和。
  maxSum is the greatest sum among all subarrays seen so far.

如果之前的 currentSum 为负数，它只会降低后续子数组的总和，所以应从当前元素重新开始。
If the previous currentSum is negative, keeping it can only reduce any future sum, so start again at the current element.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  let currentSum = nums[0];
  let maxSum = nums[0];

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

  return maxSum;
}

currentSum 和 maxSum 必须初始化为 nums[0]，不能初始化为 0，否则全为负数的数组会错误地返回空子数组的和 0。
Initialize currentSum and maxSum with nums[0], not 0; otherwise, an all-negative array would incorrectly return 0, the sum of an empty subarray.

执行过程 / Walkthrough

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例：
For nums = [-2,1,-3,4,-1,2,1,-5,4]:

最终 maxSum = 6，对应子数组 [4,-1,2,1]。
The final maxSum is 6, corresponding to subarray [4,-1,2,1].

Kadane 算法复杂度 / Kadane Complexity

• 时间复杂度：O(n)，数组只遍历一次。
  Time: O(n), because the array is traversed once.
• 空间复杂度：O(1)，只使用两个额外变量。
  Space: O(1), because only two extra variables are used.

解题思路二：分治 / Approach 2: Divide and Conquer

将数组从中间分为左右两半。区间 [left, right] 中的最大子数组只可能属于以下三种情况之一：
Split the array into left and right halves. The maximum subarray inside [left, right] must be one of three types:

1. 完全位于左半部分。
   Entirely inside the left half.
2. 完全位于右半部分。
   Entirely inside the right half.
3. 跨越中点，同时包含左半部分的后缀和右半部分的前缀。
   Crosses the midpoint, combining a suffix of the left half with a prefix of the right half.

递归求出前两种情况，再从中点向左右扫描求出跨越中点的最大和，最后返回三者最大值。
Recursively solve the first two cases, scan outward from the midpoint to find the best crossing sum, and return the maximum of all three.

JavaScript 实现 / JavaScript Implementation

function maxSubArrayDivideAndConquer(nums) {
  function solve(left, right) {
    if (left === right) {
      return nums[left];
    }

    const mid = left + Math.floor((right - left) / 2);
    const leftMax = solve(left, mid);
    const rightMax = solve(mid + 1, right);

    let bestLeftSuffix = -Infinity;
    let sum = 0;

    for (let i = mid; i >= left; i--) {
      sum += nums[i];
      bestLeftSuffix = Math.max(bestLeftSuffix, sum);
    }

    let bestRightPrefix = -Infinity;
    sum = 0;

    for (let i = mid + 1; i <= right; i++) {
      sum += nums[i];
      bestRightPrefix = Math.max(bestRightPrefix, sum);
    }

    const crossingMax = bestLeftSuffix + bestRightPrefix;
    return Math.max(leftMax, rightMax, crossingMax);
  }

  return solve(0, nums.length - 1);
}

分治复杂度 / Divide-and-Conquer Complexity

每层递归会对当前区间进行线性扫描，递归树共有 O(log n) 层，因此：
Each recursion level performs a linear total scan across its intervals, and the recursion tree has O(log n) levels. Therefore:

• 时间复杂度 / Time: O(n log n)
• 空间复杂度 / Space: O(log n)，用于递归调用栈。
  The recursion stack uses O(log n) space.

Kadane 算法的时间和空间复杂度更优；分治解法主要用于理解最大子数组的结构以及练习分治思想。
Kadane's algorithm has better time and space complexity. The divide-and-conquer method is mainly valuable for understanding the problem's structure and practicing the paradigm.

动态规划数组写法 / DP Array Version

Kadane 算法也可以显式写成动态规划数组：
Kadane's algorithm can also be expressed with an explicit DP array:

function maxSubArrayWithDP(nums) {
  const dp = new Array(nums.length);
  dp[0] = nums[0];
  let maxSum = dp[0];

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

  return maxSum;
}

• 时间复杂度 / Time: O(n)
• 空间复杂度 / Space: O(n)

由于 dp[i] 只依赖 dp[i - 1]，可以用一个变量替代整个数组，这正是空间优化后的 Kadane 算法。
Because dp[i] depends only on dp[i - 1], one variable can replace the whole array, producing the space-optimized Kadane algorithm.

易错点 / Common Pitfalls

• 子数组必须连续，不能跳过中间的负数后拼接两段。
  A subarray must be contiguous; two separated portions cannot be joined by skipping negative values.
• 子数组不能为空，即使所有元素都是负数，也必须选择其中一个元素。
  The subarray cannot be empty; even if all values are negative, one element must be selected.
• maxSum 不能初始化为 0，否则全负数组会得到错误结果。
  Do not initialize maxSum to 0, or all-negative arrays will produce an incorrect result.
• currentSum 表示必须以当前位置结尾的最大和，而 maxSum 表示全局最大和。
  currentSum is the maximum sum ending at the current position, while maxSum is the global maximum.
• 题目只要求返回最大和，不要求返回子数组本身。
  The problem asks only for the maximum sum, not the subarray itself.
• 分治解法必须考虑跨越中点的子数组，不能只比较左右两半。
  The divide-and-conquer solution must include subarrays crossing the midpoint, not just the two halves.