在分治算法中，我们递归求解一个问题。每层递归应用如下三个步骤:

  • 分解(Divide)步骤：将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小
  • 解决(Conquer)步骤：递归求解出子问题，如果子问题的规模足够小，则停止递归，直接求解。
  • 合并(Combine)步骤：将子问题的解组合成原问题的解。

当子问题足够大，需要递归求解时，我们称之为递归情况（recursive case）。当子问题变的足够小，不在需要递归时，我们说已经“触底”，进入了基本情况(base case)。

最大子数组问题

假设我们要寻找子数组A[low,height]的最大子数组。使用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是说，找到最大的子数组的中央位置，比如mid 然后考虑求解两个子数组A[low…mid]和A[mid+1…height].A[low,hight]的任何连续子数组A[i…j]所处的位置必然是以下三种情况之一:

  • 完全位于子数组A[low…mid]中，因此low<=i<=j<=mid
  • 完全位于子数组A[mid+1…hight]中，因此mid+1<=i<=j<=height
  • 跨越了中点，因此low<=i<=mid<j<=height

image.png

  2. /**
  3.  * 跨越中点的处理函数
  4.  * @param {number[]} arr  数组
  5.  * @param {number} low 起始位置
  6.  * @param {number} middle 中间位置
  7.  * @param {number} height  终止位置
  8.  */
  9. const maxCorssingSum = (arr, low, middle, height) => {
  10.     let sum = 0;
  11.     let leftSum = Number.MIN_VALUE;
  12.     for (let index = middle; index >= low; index--) {
  13.         sum += arr[index];
  14.         if (sum > leftSum) {
  15.             leftSum = sum;
  16.         }
  17.     }
  18.     sum = 0;
  19.     let rightSum = Number.MIN_VALUE;
  20.     for (let index = middle + 1; index <= height; index++) {
  21.         sum += arr[index];
  22.         if (sum > rightSum) {
  23.             rightSum = sum;
  24.         }
  25.     }
  27.     return Math.max(
  28.         leftSum + rightSum,
  29.         leftSum,
  30.         rightSum
  31.     )
  32. }
  34. /**
  35.  * 最大子数组问题求解函数
  36.  * @param {number[]} arr 数组
  37.  * @param {number} low  起始位置
  38.  * @param {number} height 终止位置
  39.  */
  40. const maxSubArraySum = (arr, low, height) => {
  41.     // 位置一致 
  42.     if (low === height) return arr[low];
  43.     const mid = (low + height) >> 1;
  44.     return Math.max(
  45.         maxSubArraySum(arr, low, mid),
  46.         maxSubArraySum(arr, mid + 1, height),
  47.         maxCorssingSum(arr, low, mid, height)
  48.     )
  49. }