0053. 最大子序和

题目地址(53. 最大子序和)

题目描述

1
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
2
3
示例:
4
5
输入: [-2,1,-3,4,-1,2,1,-5,4]
6
输出: 6
7
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
8
进阶:
9
10
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
Copied!

前置知识

公司

  • 阿里
  • 百度
  • 字节
  • 腾讯
  • bloomberg
  • linkedin
  • microsoft

思路

这道题求解连续最大子序列和,以下从时间复杂度角度分析不同的解题思路。

解法一 - 暴力解 (暴力出奇迹, 噢耶!)

一般情况下,先从暴力解分析,然后再进行一步步的优化。
原始暴力解:(超时)
求子序列和,那么我们要知道子序列的首尾位置,然后计算首尾之间的序列和。用 2 个 for 循环可以枚举所有子序列的首尾位置。 然后用一个 for 循环求解序列和。这里时间复杂度太高,O(n^3).
复杂度分析
  • 时间复杂度:$O(N ^ 3)$, 其中 N 是数组长度
  • 空间复杂度:$O(1)$

解法二 - 前缀和 + 暴力解

优化暴力解: (震惊,居然 AC 了)
在暴力解的基础上,用前缀和我们可以优化到暴力解O(n^2), 这里以空间换时间。 这里可以使用原数组表示prefixSum, 省空间。
求序列和可以用前缀和(prefixSum) 来优化,给定子序列的首尾位置(l, r), 那么序列和 subarraySum=prefixSum[r] - prefixSum[l - 1]; 用一个全局变量maxSum, 比较每次求解的子序列和,maxSum = max(maxSum, subarraySum).
复杂度分析
  • 时间复杂度:$O(N ^ 2)$, 其中 N 是数组长度
  • 空间复杂度:$O(N)$
如果用更改原数组表示前缀和数组,空间复杂度降为O(1)
但是时间复杂度还是太高,还能不能更优化。答案是可以,前缀和还可以优化到O(n).

解法三 - 优化前缀和 - from @lucifer

我们定义函数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,2,...,i-1,中的最小值即可。 因此我们需要 用一个变量来维护这个最小值,还需要一个变量维护最大值。
复杂度分析
  • 时间复杂度:$O(N)$, 其中 N 是数组长度
  • 空间复杂度:$O(1)$

解法四 - 分治法

我们把数组nums以中间位置(m)分为左(left)右(right)两部分. 那么有, left = nums[0]...nums[m - 1]right = nums[m + 1]...nums[n-1]
最大子序列和的位置有以下三种情况:
  1. 1.
    考虑中间元素nums[m], 跨越左右两部分,这里从中间元素开始,往左求出后缀最大,往右求出前缀最大, 保持连续性。
  2. 2.
    不考虑中间元素,最大子序列和出现在左半部分,递归求解左边部分最大子序列和
  3. 3.
    不考虑中间元素,最大子序列和出现在右半部分,递归求解右边部分最大子序列和
分别求出三种情况下最大子序列和,三者中最大值即为最大子序列和。
举例说明,如下图:
复杂度分析
  • 时间复杂度:$O(NlogN)$, 其中 N 是数组长度
  • 空间复杂度:$O(logN)$

解法五 - 动态规划

动态规划的难点在于找到状态转移方程,
dp[i] - 表示到当前位置 i 的最大子序列和
状态转移方程为: dp[i] = max(dp[i - 1] + nums[i], nums[i])
初始化:dp[0] = nums[0]
从状态转移方程中,我们只关注前一个状态的值,所以不需要开一个数组记录位置所有子序列和,只需要两个变量,
currMaxSum - 累计最大和到当前位置i
maxSum - 全局最大子序列和:
  • currMaxSum = max(currMaxSum + nums[i], nums[i])
  • maxSum = max(currMaxSum, maxSum)
如图:
复杂度分析
  • 时间复杂度:$O(N)$, 其中 N 是数组长度
  • 空间复杂度:$O(1)$

关键点分析

  1. 1.
    暴力解,列举所有组合子序列首尾位置的组合,求解最大的子序列和, 优化可以预先处理,得到前缀和
  2. 2.
    分治法,每次从中间位置把数组分为左右中三部分, 分别求出左右中(这里中是包括中间元素的子序列)最大和。对左右分别深度递归,三者中最大值即为当前最大子序列和。
  3. 3.
    动态规划,找到状态转移方程,求到当前位置最大和。

代码 (Java/Python3/Javascript)

解法二 - 前缀和 + 暴力

Java code
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!
Python3 code (TLE)
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!
Javascript code from @lucifer
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 code
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!
Python3 code
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!
Javascript code from @lucifer
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 code
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!
Python3 code
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!
Javascript code from @lucifer
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 code
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!
Python3 code
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!
Javascript code from @lucifer
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!

扩展

  • 如果数组是二维数组,求最大子数组的和?
  • 如果要求最大子序列的乘积?

相似题

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。