分治法求最大子序和的核心是将数组二分，最大和必在左半、右半或跨越中点的子数组中；需分别递归求解左右部分，并从中心向两侧扩展计算最大跨越和，时间复杂度O(n log n)，空间复杂度O(log n)。
分治法求最大子序和的核心思想是：把数组不断二分，最大子序和必然出现在左半部分、右半部分，或横跨中点的连续子数组中。关键在于高效处理“跨越中点”的情况。
分治三步走：分解、解决、合并
将原问题拆解为三个子问题：
-
左半部分的最大子序和：递归求解
[left, mid] -
右半部分的最大子序和：递归求解
[mid+1, right] -
跨越中点的最大子序和：从
mid向左扩展找最大左延伸和，再从mid+1向右扩展找最大右延伸和，二者相加
跨越中点的计算要小心边界
这不是简单取左右最大值相加——必须保证连续性。正确做法是：
- 设
leftSum = Integer.MIN_VALUE，从mid往左逐个累加，实时更新最大值 - 设
rightSum = Integer.MIN_VALUE，从mid+1往右逐个累加，实时更新最大值 - 跨越和 =
leftSum + rightSum
例如数组 [−2,1,−3,4,−1,2,1,−5,4]，中点在索引 3（值为 4），向左最大延伸是 4（仅自身），向右是 −1+2+1=2，跨越和为 6，对应子数组 [4,−1,2,1]。
JavaStoryDevelop
下载
你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。 它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在
立即学习“Java免费学习笔记（深入）”；
递归终止与时间复杂度
当 left == right 时直接返回该元素值，这是最小规模子问题。
- 时间复杂度：每次划分两半，合并耗时 O(n)，总时间为 O(n log n)
- 空间复杂度：递归栈深度 O(log n)
- 相比动态规划（O(n) 时间），分治稍慢但思路清晰，适合理解“子问题独立性”和“合并策略”
代码结构要点
写一个辅助递归函数 maxSubArray(int[] nums, int left, int right)，主函数调用 maxSubArray(nums, 0, nums.length-1) 即可。注意整数溢出风险，初始值用 Integer.MIN_VALUE 而非 0。
