LeetCode53-最大子序和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/maximum-subarray/

中文链接：https://leetcode-cn.com/problems/maximum-subarray/

题目详述

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

示例:

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

进阶:

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

题目详解

动态规划经典题目。运用两个变量 maxSum、curSum，遍历一次即可。

  • 首先初始化 maxSum、curSum 为数组中的第一个元素，maxSum 用来记录最终结果，curSum 用来记录当前的和。
  • 只有 curSum > 0 时，nums[i] 加上 curSum 才会得到一个更大的和。
  • 当 curSum < 0 时，nums[i] 加上 curSum 反而会使加和变小，故直接令 curSum = nums[i] 。
  • 每次比较 maxSum 和 curSum，当 curSum > maxSum 时，更新 maxSum。
1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00053 {

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int curSum = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            curSum = curSum > 0 ? curSum + nums[i] : nums[i];
            maxSum = Math.max(maxSum, curSum);
        }
        return maxSum;
    }
}

分治法也可以解决本题，时间复杂度为 O(nlogn)，上面 DP 的时间复杂度为 O(n)。

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
public class LeetCode_00053 {

    // 分治
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return maxSubArray(nums, 0, nums.length - 1);
    }

    private int maxSubArray(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return Integer.MIN_VALUE;
        }
        if (lo == hi) {
            return nums[lo];
        }
        // 分解成两个子问题
        int mid = lo + (hi - lo) / 2;
        int leftSub = maxSubArray(nums, lo, mid - 1);
        int rightSub = maxSubArray(nums, mid + 1, hi);
        int leftSum = 0;
        int tmp = 0;
        for (int i = mid - 1; i >= lo; --i) {
            tmp += nums[i];
            leftSum = Math.max(leftSum, tmp);
        }
        int rightSum = 0;
        tmp = 0;
        for (int i = mid + 1; i <= hi; ++i) {
            tmp += nums[i];
            rightSum = Math.max(rightSum, tmp);
        }
        // 包含 mid 与 不包含 mid 取较大值
        return Math.max(Math.max(leftSub, rightSub), nums[mid] + leftSum + rightSum);
    }
}