Skip to content

导论¶

笔记散乱，尚未整理

一个栗子¶

最大连续子数组¶

题设¶

给定一个数组 A[0,...,n-1]，求连续子数组，使该子数组和最大。

例如:

数组：1, -2, 3, 10, -4, 7, 2, -5

最大子数组: 3, 10, -4, 7, 2

常用解法¶

暴力法
分治法
分析法
动态规划法

暴力法¶

代码¶

function MaxSubArray(A) {
  let n = A.length;
  let maxSum = A[0];

  let currentSum;
  for(let i = 0; i < n; i++) {
    for(let j = i; j < n; j++) {
      currentSum = 0;
      for(let k = i; k <= j; k++) {
        currentSum += A[k];
      }
      if (currentSum > maxSum) {
        maxSum = currentSum;
      }
    }
  }

  return maxSum;
}

复杂度¶

时间复杂度 O(n^3)

分治法¶

算法思想¶

将数组从中分开，那么最法子数组要么完全在左半边，要么完全在右半边，要么跨立在分界点上。
完全在左/右半边，可以递归解决；
跨立在分界点上：左数组的最大后缀 + 右数组的最大前缀。

代码¶

function MaxSub(A, from, to) {
  if (from === to) {
    return A[from];
  }

  let middle = Math.floor((from + to) / 2);
  let max1 = MaxSub(A, from, middle); // 左递归
  let max2 = MaxSub(A, middle + 1, to); // 右递归

  let left = A[middle], now = A[middle]
  for(let i = middle - 1; i >= from; i--) {
    now += A[i];
    left = left >= now ? left : now;
  }

  let right = A[middle + 1];
  now = A[middle + 1];
  for(let i = middle + 2; i <= to; i++) {
    now += A[i];
    right = right >= now ? right : now;
  }
  let max3 = left + right; // 跨立左右

  return max(max1, max2, max3);
}

function max() {
  const args = Array.prototype.slice.call(arguments);

  let _max = args[0];
  args.forEach(i => _max = _max >= i ? _max : i);

  return _max; 
}

复杂度¶

时间递推关系: T(n) = 2 * T(n - 1) + c * n, c 为常量
所以，时间复杂度: T(n) = O(nlogn)