最大子数组和（leetcode-53）

题目描述

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

解法

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  let len = nums.length, result = Number.MIN_SAFE_INTEGER;
  for (let i = 0; i < len; i++) {
    let sum = 0, tempResult = nums[i];
    for (let j = i; j < len; j++) {
      sum += nums[j];
      tempResult = Math.max(tempResult, sum);
    }
    result = Math.max(result, tempResult);
  }
  return result;
};

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])         // => 6

分治法

最大子数组和要么在左半边，要么在右半边，要么是穿过中间，对于左右边的序列，可以用递归处理，中间则可直接计算

  • 时间复杂度 —— O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  return findMax(nums, 0, nums.length - 1);
}

// 计算数组arr中从left到right的子数组的最大和
function findMax(arr, left, right) {
  if (left === right) {
    return arr[left]
  } else {
    // 取left到right的中间位置
    let mid = Math.floor((left + right) / 2);

    // 分别计算左半边、右半边和穿过mid的子数组的最大和
    let leftMax = findMax(arr, left, mid),
        rightMax = findMax(arr, mid + 1, right),
        crossMax = findCrossMax(arr, mid, left, right);

    // 取其中的最大值
    return Math.max(leftMax, rightMax, crossMax);
  }
}

// 计算数组arr中从left到right且穿过mid的子数组的最大和
function findCrossMax(arr, mid, left, right) {

  // 计算mid左侧的最大和
  let leftMax = arr[mid], leftSum = 0;
  for (let i = mid; i >= left; i--) {
    leftSum += arr[i];
    leftMax = Math.max(leftMax, leftSum);
  }

  // 计算mid右侧的最大和
  let rightMax = arr[mid + 1], rightSum = 0;
  for (let i = mid + 1; i <= right; i++) {
    rightSum += arr[i];
    rightMax = Math.max(rightMax, rightSum);
  }

  // 返回二者之和
  return leftMax + rightMax;
}

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])         // => 6

动态规划法

遍历数组，用sum记录当前位置前子数组最大和，有

选择最大的sum即是最终解

  • 时间复杂度 —— O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  let result = nums[0], sum = nums[0], len = nums.length;
  for (let i = 1; i < len; i++) {
    sum = Math.max(nums[i], sum + nums[i]);
    result = Math.max(result, sum);
  }
  return result;
}

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])         // => 6

另一种解法

首先对数组进行遍历，如果sum > 0，则说明sum对结果有增益效果，则sum保留并加上当前遍历数字；如果sum <= 0，则说明sum对结果无增益效果，需要舍弃，则sum直接更新为当前遍历数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums
 * @return {number}
 */
function maxSubArray(nums) {
  let sum = 0, result = nums[0], len = nums.length;
  for (let i = 0; i < len; i++) {
    sum = sum > 0 ? sum + nums[i] : nums[i];
    result = Math.max(result, sum);
  }
  return result;
}

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])         // => 6