分治法求最大子序和的核心是将数组二分，最大和必在左半、右半或跨越中点的子数组中；需分别递归求解左右部分，并从中心向两侧扩展计算最大跨越和，时间复杂度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]。
递归终止与时间复杂度
当 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。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
