【LeetCode-简单】53. 最大子序和

By 大Van家 on 2021-09-09
阅读时间 4 分钟
文章共 995
阅读量

要点:滑动窗口、动态规划

描述

1
2
3
4
5
6
7
8
9
10
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6
进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

关键点

方法一、前缀和+暴力解

求序列和可以用前缀和(prefixSum) 来优化,给定子序列的首尾位置(l, r), 那么序列和 subarraySum=prefixSum[r] - prefixSum[l - 1]; 用一个全局变量maxSum, 比较每次求解的子序列和,maxSum = max(maxSum, subarraySum).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
const len = nums.length;
let max = -Number.MAX_VALUE;
let sum = 0;
for (let i = 0; i < len; i++) {
sum = 0;
for (let j = i; j < len; j++) {
sum += nums[j];
max = Math.max(max, sum)
//if (sum > max) {
// max = sum;
//}
}
}
return max;
};
  • 203/203 cases passed (172 ms)
  • Your runtime beats 7.92 % of javascript submissions
  • Your memory usage beats 76.04 % of javascript submissions (39.2 MB)

时间复杂度:$O(N ^ 2)$, 其中 N 是数组长度

空间复杂度:$O(N)$

方法二、优化前缀和

我们定义函数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,中的最小值即可。 因此我们需要 用一个变量来维护这个最小值,还需要一个变量维护最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
var prev = 0;
var max = -Number.MAX_VALUE;

for (var i = 0; i < nums.length; i++) {
prev = Math.max(prev + nums[i], nums[i]);
max = Math.max(max, prev);
}
return max;
};
  • 203/203 cases passed (72 ms)
  • Your runtime beats 84.33 % of javascript submissions
  • Your memory usage beats 85.98 % of javascript submissions (39.1 MB)

时间复杂度:$O(N)$, 其中 N 是数组长度

空间复杂度:$O(1)$

方法三、分治法

我们把数组nums以中间位置(m)分为左(left)右(right)两部分. 那么有, left = nums[0]...nums[m - 1]right = nums[m + 1]...nums[n-1]

最大子序列和的位置有以下三种情况:

  1. 考虑中间元素nums[m], 跨越左右两部分,这里从中间元素开始,往左求出后缀最大,往右求出前缀最大, 保持连续性。
  2. 不考虑中间元素,最大子序列和出现在左半部分,递归求解左边部分最大子序列和
  3. 不考虑中间元素,最大子序列和出现在右半部分,递归求解右边部分最大子序列和

分别求出三种情况下最大子序列和,三者中最大值即为最大子序列和。

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
function helper(list, m, n) {
if (m === n) return list[m];
let sum = 0;
let lmax = -Number.MAX_VALUE;
let rmax = -Number.MAX_VALUE;
const mid = ((n - m) >> 1) + m;

const l = helper(list, m, mid);
const r = helper(list, mid + 1, n);
for (let i = mid; i >= m; i--) {
sum += list[i];
if (sum > lmax) lmax = sum;
}

sum = 0;

for (let i = mid + 1; i <= n; i++) {
sum += list[i];
if (sum > rmax) rmax = sum;
}

return Math.max(l, r, lmax + rmax);
}

function LSS(list) {
return helper(list, 0, list.length - 1);
}
  • 203/203 cases passed (76 ms)
  • Your runtime beats 70.48 % of javascript submissions
  • Your memory usage beats 22.56 % of javascript submissions (39.5 MB)

时间复杂度:$O(NlogN)$, 其中 N 是数组长度

空间复杂度:$O(logN)$

方法四、动态规划

1
2
3
4
5
6
7
8
9
10
function LSS(list) {
const len = list.length;
let max = list[0];
for (let i = 1; i < len; i++) {
list[i] = Math.max(0, list[i - 1]) + list[i];
if (list[i] > max) max = list[i];
}

return max;
}

时间复杂度:$O(N)$, 其中 N 是数组长度

空间复杂度:$O(1)$


Tips: Please indicate the source and original author when reprinting or quoting this article.