最大子序和

发表于 | 分类于 |
字数统计: 665 字 | 阅读时长 ≈ 3 分钟

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

 

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [0]
输出：0

示例 4：
输入：nums = [-1]
输出：-1

示例 5：
输入：nums = [-100000]
输出：-100000

方法一：动态规划

  • 首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 max
  • 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
  • 每次比较 sum 和 max的大小，将最大值置为max，遍历结束返回结果
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
class Solution {
  public int maxSubArray(int[] nums) {
    int max = nums[0];
    int sum = 0;
    for(int num: nums) {
      if(sum > 0) {
        sum += num;
      } else {
        sum = num;
      }
      max = Math.max(max, sum);
    }
    return max;
  }
}

var maxSubArray = function(nums) {
  let max = nums[0], sum = 0
  for(let num of nums) {
    if(sum > 0) {
      sum += num
    } else {
      sum = num
    }
    max = Math.max(sum, max)
  }
  return max
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了95.61%的用户

  • 内存消耗：38.4 MB, 在所有 Java 提交中击败了41.85%的用户

延伸——获取最大序列的起始和结束位置

使用动态规划找到位置，需要注意：

  • 遍历子序的同时，更新子序的结束位置
  • 如果为无增益，需要重置起始、结束位置
  • 比较最大值时，需要更新起始、结束位置
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
class Solution {
  public int maxSubArray(int[] nums) {
    int max = nums[0], sum = 0;
    int subLeft = 0, subRight = 0;
    int left = 0, right = 0;
    for(int i = 0; i < nums.length; i++) {
      if(sum > 0) {
        sum += nums[i];
        subRight++;
      } else {
        sum = nums[i];
        subLeft = i;
        subRight = i;
      }

      if(sum > max) {
        max = sum;
        left = subLeft;
        right = subRight;
      }
    }
    System.out.println("[" + left + ","+ right +"]");
    return max;
  }
}

var maxSubArray = function(nums) {
    let max = nums[0], sum = 0
    let subLeft = 0, subRight = 0, left = 0, right = 0
    for(let i = 0; i < nums.length; i++) {
        if(sum > 0) {
            sum += nums[i]
            subRight++
        } else {
            sum = nums[i]
            subLeft = i
            subRight = i
        }
        if(sum > max) {
            max = sum
            left = subLeft
            right = subRight
        }
    }
    console.log(left, right)
    return max
};