一文看懂《最大子序列和问题》
最大子序列和是一道经典的算法题, leetcode 也有原题《53.maximum-sum-subarray》,今天我们就来彻底攻克它。

题目描述

求取数组中最大连续子序列和,例如给定数组为 A = [1, 3, -2, 4, -5], 则最大连续子序列和为 6,即 1 + 3 +(-2)+ 4 = 6。 去
首先我们来明确一下题意。
  • 题目说的子数组是连续的
  • 题目只需要求和,不需要返回子数组的具体位置。
  • 数组中的元素是整数,但是可能是正数,负数和 0。
  • 子序列的最小长度为 1。
比如:
  • 对于数组 [1, -2, 3, 5, -3, 2], 应该返回 3 + 5 = 8
  • 对于数组 [0, -2, 3, 5, -1, 2], 应该返回 3 + 5 + -1 + 2 = 9
  • 对于数组 [-9, -2, -3, -5, -3], 应该返回 -2

解法一 - 暴力法(超时法)

一般情况下,先从暴力解分析,然后再进行一步步的优化。

思路

我们来试下最直接的方法,就是计算所有的子序列的和,然后取出最大值。 记 Sum[i,....,j]为数组 A 中第 i 个元素到第 j 个元素的和,其中 0 <= i <= j < n, 遍历所有可能的 Sum[i,....,j] 即可。
我们去枚举以 0,1,2...n-1 开头的所有子序列即可, 对于每一个开头的子序列,我们都去枚举从当前开始到 n-1 的所有情况。
这种做法的时间复杂度为 O(N^2), 空间复杂度为 O(1)。

代码

JavaScript:
1
function LSS(list) {
2
const len = list.length;
3
let max = -Number.MAX_VALUE;
4
let sum = 0;
5
for (let i = 0; i < len; i++) {
6
sum = 0;
7
for (let j = i; j < len; j++) {
8
sum += list[j];
9
if (sum > max) {
10
max = sum;
11
}
12
}
13
}
14
15
return max;
16
}
Copied!
Java:
1
class MaximumSubarrayPrefixSum {
2
public int maxSubArray(int[] nums) {
3
int len = nums.length;
4
int maxSum = Integer.MIN_VALUE;
5
int sum = 0;
6
for (int i = 0; i < len; i++) {
7
sum = 0;
8
for (int j = i; j < len; j++) {
9
sum += nums[j];
10
maxSum = Math.max(maxSum, sum);
11
}
12
}
13
return maxSum;
14
}
15
}
Copied!
Python 3:
1
import sys
2
class Solution:
3
def maxSubArray(self, nums: List[int]) -> int:
4
n = len(nums)
5
maxSum = -sys.maxsize
6
sum = 0
7
for i in range(n):
8
sum = 0
9
for j in range(i, n):
10
sum += nums[j]
11
maxSum = max(maxSum, sum)
12
13
return maxSum
Copied!
空间复杂度非常理想,但是时间复杂度有点高。怎么优化呢?我们来看下下一个解法。

解法二 - 分治法

思路

我们来分析一下这个问题, 我们先把数组平均分成左右两部分。
此时有三种情况:
  • 最大子序列全部在数组左部分
  • 最大子序列全部在数组右部分
  • 最大子序列横跨左右数组
对于前两种情况,我们相当于将原问题转化为了规模更小的同样问题。
对于第三种情况,由于已知循环的起点(即中点),我们只需要进行一次循环,分别找出 左边和右边的最大子序列即可。
所以一个思路就是我们每次都对数组分成左右两部分,然后分别计算上面三种情况的最大子序列和, 取出最大的即可。
举例说明,如下图:
(by snowan)
这种做法的时间复杂度为 O(N*logN), 空间复杂度为 O(1)。

代码

JavaScript:
1
function helper(list, m, n) {
2
if (m === n) return list[m];
3
let sum = 0;
4
let lmax = -Number.MAX_VALUE;
5
let rmax = -Number.MAX_VALUE;
6
const mid = ((n - m) >> 1) + m;
7
const l = helper(list, m, mid);
8
const r = helper(list, mid + 1, n);
9
for (let i = mid; i >= m; i--) {
10
sum += list[i];
11
if (sum > lmax) lmax = sum;
12
}
13
14
sum = 0;
15
16
for (let i = mid + 1; i <= n; i++) {
17
sum += list[i];
18
if (sum > rmax) rmax = sum;
19
}
20
21
return Math.max(l, r, lmax + rmax);
22
}
23
24
function LSS(list) {
25
return helper(list, 0, list.length - 1);
26
}
Copied!
Java:
1
class MaximumSubarrayDivideConquer {
2
public int maxSubArrayDividConquer(int[] nums) {
3
if (nums == null || nums.length == 0) return 0;
4
return helper(nums, 0, nums.length - 1);
5
}
6
private int helper(int[] nums, int l, int r) {
7
if (l > r) return Integer.MIN_VALUE;
8
int mid = (l + r) >>> 1;
9
int left = helper(nums, l, mid - 1);
10
int right = helper(nums, mid + 1, r);
11
int leftMaxSum = 0;
12
int sum = 0;
13
// left surfix maxSum start from index mid - 1 to l
14
for (int i = mid - 1; i >= l; i--) {
15
sum += nums[i];
16
leftMaxSum = Math.max(leftMaxSum, sum);
17
}
18
int rightMaxSum = 0;
19
sum = 0;
20
// right prefix maxSum start from index mid + 1 to r
21
for (int i = mid + 1; i <= r; i++) {
22
sum += nums[i];
23
rightMaxSum = Math.max(sum, rightMaxSum);
24
}
25
// max(left, right, crossSum)
26
return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
27
}
28
}
Copied!
Python 3 :
1
import sys
2
class Solution:
3
def maxSubArray(self, nums: List[int]) -> int:
4
return self.helper(nums, 0, len(nums) - 1)
5
def helper(self, nums, l, r):
6
if l > r:
7
return -sys.maxsize
8
mid = (l + r) // 2
9
left = self.helper(nums, l, mid - 1)
10
right = self.helper(nums, mid + 1, r)
11
left_suffix_max_sum = right_prefix_max_sum = 0
12
sum = 0
13
for i in reversed(range(l, mid)):
14
sum += nums[i]
15
left_suffix_max_sum = max(left_suffix_max_sum, sum)
16
sum = 0
17
for i in range(mid + 1, r + 1):
18
sum += nums[i]
19
right_prefix_max_sum = max(right_prefix_max_sum, sum)
20
cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid]
21
return max(cross_max_sum, left, right)
Copied!

解法三 - 动态规划

思路

我们来思考一下这个问题, 看能不能将其拆解为规模更小的同样问题,并且能找出 递推关系。
我们不妨假设问题 Q(list, i) 表示 list 中以索引 i 结尾的情况下最大子序列和, 那么原问题就转化为 Q(list, i), 其中 i = 0,1,2...n-1 中的最大值。
我们继续来看下递归关系,即 Q(list, i)和 Q(list, i - 1)的关系, 即如何根据 Q(list, i - 1) 推导出 Q(list, i)。
如果已知 Q(list, i - 1), 我们可以将问题分为两种情况,即以索引为 i 的元素终止, 或者只有一个索引为 i 的元素。
  • 如果以索引为 i 的元素终止, 那么就是 Q(list, i - 1) + list[i]
  • 如果只有一个索引为 i 的元素,那么就是 list[i]
分析到这里,递推关系就很明朗了,即Q(list, i) = Math.max(0, Q(list, i - 1)) + list[i]
举例说明,如下图:
(by snowan)
这种算法的时间复杂度 O(N), 空间复杂度为 O(1)

代码

JavaScript:
1
function LSS(list) {
2
const len = list.length;
3
let max = list[0];
4
for (let i = 1; i < len; i++) {
5
list[i] = Math.max(0, list[i - 1]) + list[i];
6
if (list[i] > max) max = list[i];
7
}
8
9
return max;
10
}
Copied!
Java:
1
class MaximumSubarrayDP {
2
public int maxSubArray(int[] nums) {
3
int currMaxSum = nums[0];
4
int maxSum = nums[0];
5
for (int i = 1; i < nums.length; i++) {
6
currMaxSum = Math.max(currMaxSum + nums[i], nums[i]);
7
maxSum = Math.max(maxSum, currMaxSum);
8
}
9
return maxSum;
10
}
11
}
Copied!
Python 3:
1
class Solution:
2
def maxSubArray(self, nums: List[int]) -> int:
3
n = len(nums)
4
max_sum_ending_curr_index = max_sum = nums[0]
5
for i in range(1, n):
6
max_sum_ending_curr_index = max(max_sum_ending_curr_index + nums[i], nums[i])
7
max_sum = max(max_sum_ending_curr_index, max_sum)
8
9
return max_sum
Copied!

解法四 - 数学分析

思路

我们来通过数学分析来看一下这个题目。
我们定义函数 S(i) ,它的功能是计算以 0(包括 0)开始加到 i(包括 i)的值。
那么 S(j) - S(i - 1) 就等于 从 i 开始(包括 i)加到 j(包括 j)的值。
我们进一步分析,实际上我们只需要遍历一次计算出所有的 S(i), 其中 i 等于 0,1,2....,n-1。 然后我们再减去之前的 S(k),其中 k 等于 0,1,i - 1,中的最小值即可。 因此我们需要 用一个变量来维护这个最小值,还需要一个变量维护最大值。
这种算法的时间复杂度 O(N), 空间复杂度为 O(1)。
其实很多题目,都有这样的思想, 比如之前的《每日一题 - 电梯问题》。

代码

JavaScript:
1
function LSS(list) {
2
const len = list.length;
3
let max = list[0];
4
let min = 0;
5
let sum = 0;
6
for (let i = 0; i < len; i++) {
7
sum += list[i];
8
if (sum - min > max) max = sum - min;
9
if (sum < min) {
10
min = sum;
11
}
12
}
13
14
return max;
15
}
Copied!
Java:
1
class MaxSumSubarray {
2
public int maxSubArray3(int[] nums) {
3
int maxSum = nums[0];
4
int sum = 0;
5
int minSum = 0;
6
for (int num : nums) {
7
// prefix Sum
8
sum += num;
9
// update maxSum
10
maxSum = Math.max(maxSum, sum - minSum);
11
// update minSum
12
minSum = Math.min(minSum, sum);
13
}
14
return maxSum;
15
}
16
}
Copied!
Python 3:
1
class Solution:
2
def maxSubArray(self, nums: List[int]) -> int:
3
n = len(nums)
4
maxSum = nums[0]
5
minSum = sum = 0
6
for i in range(n):
7
sum += nums[i]
8
maxSum = max(maxSum, sum - minSum)
9
minSum = min(minSum, sum)
10
11
return maxSum
Copied!

总结

我们使用四种方法解决了《最大子序列和问题》, 并详细分析了各个解法的思路以及复杂度,相信下次你碰到相同或者类似的问题 的时候也能够发散思维,做到一题多解,多题一解
实际上,我们只是求出了最大的和,如果题目进一步要求出最大子序列和的子序列呢? 如果要题目允许不连续呢? 我们又该如何思考和变通?如何将数组改成二维,求解最大矩阵和怎么计算? 这些问题留给读者自己来思考。