LeetCode 补拙笔记

0. 前言

• 日期：2026.06.29
• 题目：53. 最大子数组和
• 难度：中等
• 标签：数组、动态规划、分治

1. 题目理解

问题描述 给定整数数组 nums，找出具有最大和的连续非空子数组，返回该子数组的和。

示例

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 和为 6。

2. 解题思路

核心观察

1. 动态规划（原版）：pre 代表以当前下标结尾的最大子数组和，pre = max(pre + nums[i], nums[i])，同步维护全局最大值；全程无if分支，用Math.max完成选择。
2. 分治法优化思路：将数组拆分为左右两段，结果来自三种情况：左区间最大值、右区间最大值、跨中点区间最大值；递归拆分至单个元素后合并，消除多层条件判断。

算法步骤

动态规划原版：

1. 初始化 pre、maxSum 为首元素；
2. 遍历数组从第二位开始；
3. 更新以当前元素结尾的最大子数组和；
4. 更新全局最大和，遍历结束返回。

分治版本：

1. 递归函数接收区间左右边界；
2. 边界：区间仅一个元素直接返回该值；
3. 二分中点，递归求左区间最大值、右区间最大值；
4. 从中点向左求左最大后缀和，从中点向右求右最大前缀和，相加得到跨中点区间最大值；
5. 三者取最大值作为当前区间答案。

3. 代码实现

package lc0_lc99.lc53;

public class Solution {
    public int maxSubArray(int[] nums) {
        int pre = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            maxSum = Math.max(maxSum, pre);
        }
        return maxSum;
    }
}

4. 代码优化说明

class Solution {
    public int maxSubArray(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }

    // 分治递归，计算[l,r]区间最大子数组和
    private int divide(int[] nums, int l, int r) {
        if (l == r) return nums[l];
        int mid = l + (r - l) / 2;
        int leftMax = divide(nums, l, mid);
        int rightMax = divide(nums, mid + 1, r);

        // 求跨中点区间最大值：左后缀最大 + 右前缀最大
        int leftSuffix = 0, cur = 0;
        for (int i = mid; i >= l; i--) {
            cur += nums[i];
            leftSuffix = Math.max(leftSuffix, cur);
        }
        int rightPrefix = 0;
        cur = 0;
        for (int i = mid + 1; i <= r; i++) {
            cur += nums[i];
            rightPrefix = Math.max(rightPrefix, cur);
        }
        int crossMax = leftSuffix + rightPrefix;
        // 三者取最大，无多层if分支
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }
}

5. 复杂度分析

• 动态规划原版 时间复杂度：$O(n)$，仅单次遍历数组，无if分支，Math.max完成比较 空间复杂度：$O(1)$，仅常数临时变量
• 分治版本 时间复杂度：$O(n\log n)$，二分递归深度$\log n$，每层总遍历元素$n$ 空间复杂度：$O(\log n)$，递归调用栈开销；使用Math.max消除条件分支，逻辑统一

6. 总结

• 核心：DP贪心单次遍历效率最优；分治采用二分拆分，适合分治题型考点；
• 优化亮点：分治实现全程用Math.max替代if条件判断，减少分支跳转；递归拆分逻辑清晰，覆盖全部子区间场景；
• 取舍：日常解题优先DP线性解法；面试考察分治思想时使用分治版本。