分治法

我们把数组nums以中间位置（m)分为左（left)右(right)两部分. 那么有，

left = nums[0]...nums[m - 1] 和 right = nums[m + 1]...nums[n-1]

最大子序列和的位置有以下三种情况：

分别求出三种情况下最大子序列和，三者中最大值即为最大子序列和。

举例说明，如下图：

复杂度分析

补充

补充：以"最大子序和"为例，分治三步：

• 左半部分最大子序和 —— 递归求解。
• 右半部分最大子序和 —— 递归求解。
• 横跨中点的最大子序和 —— 从中点向左累加取最大 + 向右累加取最大，二者相加。

三者取最大即答案。复杂度 O(n log n)，但实际上 Kadane 算法（动态规划）只需 O(n) 即可解决；分治的价值更多在于"分而治之"的递归思维训练（归并排序、快速排序、最近点对等都使用同一思路）。

function maxSubArray(nums, l = 0, r = nums.length - 1) {
  if (l === r) return nums[l];
  const m = (l + r) >> 1;
  const left = maxSubArray(nums, l, m);
  const right = maxSubArray(nums, m + 1, r);
  let lMax = -Infinity, rMax = -Infinity, s = 0;
  for (let i = m; i >= l; i--) { s += nums[i]; lMax = Math.max(lMax, s); }
  s = 0;
  for (let i = m + 1; i <= r; i++) { s += nums[i]; rMax = Math.max(rMax, s); }
  return Math.max(left, right, lMax + rMax);
}

来源整理自：我的有道云笔记