TNotes.leetcode

Appearance

0053. 最大子数组和【中等】

0053. 最大子数组和【中等】 ​

1. 📝 题目描述 ​

给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

子数组是数组中连续的非空元素序列。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

2. 🎯 s.1 - Kadane（DP/贪心） 算法 ​

c
int maxSubArray(int* nums, int numsSize) {
    int bestSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < numsSize; i++) {
        currentSum = currentSum > 0 ? currentSum + nums[i] : nums[i];
        if (currentSum > bestSum)
            bestSum = currentSum;
    }

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

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

  return bestSum
}
py
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best_sum = nums[0]
        current_sum = nums[0]

        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            best_sum = max(best_sum, current_sum)

        return best_sum
  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

算法思路：

  • 设 currentSum 表示“以当前位置结尾”的最大子数组和，bestSum 表示遍历过程中的全局最大值
  • 任何一个以位置 i 结尾的最大子数组，要么单独由 nums[i] 构成，要么是“以 i-1 结尾的最大子数组 + nums[i]”，这构成了最优子结构，使得贪心/动态规划的思路成立
    • 动态规划视角 dp[i] = max(dp[i-1] + nums[i], nums[i]) => 对应的状态转移方程 => currentSum=max(nums[i],currentSum+nums[i])
    • 贪心视角 => 连续和一旦为负就重置，局部最优推全局最优
  • 每次更新完 currentSum 后，用它刷新 bestSum
  • 遍历结束后，bestSum 就是答案

3. 🎯 s.2 - 分治 ​

c
int helper(int* nums, int left, int right) {
    // base case：只有一个元素
    if (left == right)
        return nums[left];

    int mid = (left + right) / 2;

    // 情况一：最大子数组在左半部分
    int leftMax = helper(nums, left, mid);

    // 情况二：最大子数组在右半部分
    int rightMax = helper(nums, mid + 1, right);

    // 情况三：最大子数组跨越中点
    // <- 从中点向左扩展，求最大和
    int leftSum = -1000000000;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > leftSum)
            leftSum = sum;
    }

    // -> 从中点右边向右扩展，求最大和
    int rightSum = -1000000000;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > rightSum)
            rightSum = sum;
    }

    int crossMax = leftSum + rightSum;

    // 三种情况取最大值
    int max = leftMax;
    if (rightMax > max)
        max = rightMax;
    if (crossMax > max)
        max = crossMax;
    return max;
}

int maxSubArray(int* nums, int numsSize) {
    return helper(nums, 0, numsSize - 1);
}
js
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  function helper(left, right) {
    // base case：只有一个元素
    if (left === right) return nums[left]

    const mid = Math.floor((left + right) / 2)

    // 情况一：最大子数组在左半部分
    const leftMax = helper(left, mid)

    // 情况二：最大子数组在右半部分
    const rightMax = helper(mid + 1, right)

    // 情况三：最大子数组跨越中点
    // <- 从中点向左扩展，求最大和
    let leftSum = -Infinity
    let sum = 0
    for (let i = mid; i >= left; i--) {
      sum += nums[i]
      leftSum = Math.max(leftSum, sum)
    }

    // -> 从中点右边向右扩展，求最大和
    let rightSum = -Infinity
    sum = 0
    for (let i = mid + 1; i <= right; i++) {
      sum += nums[i]
      rightSum = Math.max(rightSum, sum)
    }

    const crossMax = leftSum + rightSum

    // 三种情况取最大值
    return Math.max(leftMax, rightMax, crossMax)
  }

  return helper(0, nums.length - 1)
}
py
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def helper(left: int, right: int) -> int:
            # base case：只有一个元素
            if left == right:
                return nums[left]

            mid = (left + right) // 2

            # 情况一：最大子数组在左半部分
            left_max = helper(left, mid)

            # 情况二：最大子数组在右半部分
            right_max = helper(mid + 1, right)

            # 情况三：最大子数组跨越中点
            # <- 从中点向左扩展，求最大和
            left_sum = -float("inf")
            total = 0
            for i in range(mid, left - 1, -1):
                total += nums[i]
                left_sum = max(left_sum, total)

            # -> 从中点右边向右扩展，求最大和
            right_sum = -float("inf")
            total = 0
            for i in range(mid + 1, right + 1):
                total += nums[i]
                right_sum = max(right_sum, total)

            cross_max = left_sum + right_sum

            # 三种情况取最大值
            return max(left_max, right_max, cross_max)

        return helper(0, len(nums) - 1)
  • 时间复杂度：O(nlog⁡n)，每一层递归都会线性扫描当前区间来计算跨越中点的最大子数组和，递归深度为 log⁡n
  • 空间复杂度：O(log⁡n)，递归调用栈的深度为 log⁡n

算法思路：

  • 将区间 [left, right] 按中点 mid 拆成左右两半，最大子数组只可能出现在三种情况中：
    • 完全位于左半区间
    • 完全位于右半区间
    • 跨越中点
  • 前两种情况递归求解即可，分别得到 leftMax 和 rightMax
  • 对于跨越中点的情况，从 mid 向左枚举，求“必须以 mid 结尾”的最大后缀和；再从 mid + 1 向右枚举，求“必须以 mid + 1 开头”的最大前缀和，两者相加就是 crossMax
  • 最终返回 max(leftMax, rightMax, crossMax)，递归终止条件是区间中只剩一个元素，此时最大子数组和就是该元素本身

Discussions