LeetCode_95_MaximumSubarray

LeetCode

发布日期: 2022-06-12

更新日期: 2022-06-12

文章字数: 969

阅读时长: 4 分

阅读次数:

1. question: 最大子数组和（简单）

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

子数组是数组中的一个连续部分。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray

示例 1：

1
2
3

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

示例 2：

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

示例 3：

1 2	输入：nums = [5,4,-1,7,8] 输出：23

提示：

1 2	1 <= nums.length <= 105 -104 <= nums[i] <= 104

2. answers

这道题也是比较经典，其实感觉和贪心并不是很有直接关系，但是也涉及到贪心的思想了。这道题是子数组，即是连续元素和。首先想到的是暴力法，确定子数组的起始和结束位置，遍历求和。毫无疑问超时了。代码如下所示：

public class Solution_0095 {

    public int maxSubArray(int[] nums) {

        // 因为结果是int，所以保证了最坏情况下也在区间内。
        int max = Integer.MIN_VALUE;

        for (int start = 0; start < nums.length; start++) {

            int sum = 0;
            for (int end = start; end < nums.length; end++) {

                sum += nums[end];
                max = Math.max(max, sum);
            }
        }

        return max;
    }

    public static void main(String[] args) {

//        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int[] nums = {5, 4, -1, 7, 8};

        Solution_0095 s = new Solution_0095();

        System.out.println(s.maxSubArray(nums));
    }
}

超时，就意味着多了很多无用次比较。因此，尝试改进。起始元素如果是负数，那么就没必要开始累加了，进行下个子数组即可。因为是负数，显然负数只会使得最终结果更小。代码如下所示：

public int maxSubArray(int[] nums) {

    // 因为结果是int，所以保证了最坏情况下也在区间内。
    int max = Integer.MIN_VALUE;

    for (int start = 0; start < nums.length; start++) {

        if(nums[start] <= 0) continue;
        int sum = 0;
        for (int end = start; end < nums.length; end++) {

            sum += nums[end];
            max = Math.max(max, sum);
        }
    }

    if(max == Integer.MIN_VALUE){
        Arrays.sort(nums);
        max = nums[nums.length - 1];
    }

    return max;
}

但是这样做仍然超时，即还有很多无用次比较。显然，第一个子数组如果是4个元素，那么第二个子数组的前三位元素其实就不需要累加了，也不需要比较了。即相邻子数组之间的重复的部分有很多重复操作。

参考题解的做法：

只要是负数，其实就没必要向后续传递了，即此时累加应该终止，即当前子数组结束。因为负数只会使得结果变得更小。所以，遍历数组，累加，取最大值。如果累加和为负数，那么更新累加值为0，即不再像后续传递。（注意，一定要先累加，再取最大值，这样才能保证是和子数组比较；否则可能会和更新后的0比较。）

代码如下所示：

public class Solution_0095_03 {

    public int maxSubArray(int[] nums) {

        // 初始化最大值 为 某个最小的数。
        int max = Integer.MIN_VALUE;

        // 初始化子数组累加和为0
        int sums = 0;

        for (int num : nums) {

            // 先累加，判断此时的最大值。
            sums += num;
            max = Math.max(max, sums);

            // 如果加上当前数为正数，那么就有可能是最大的；所以子数组无需重新计算。
            // 如果是当前子数组累加数为负数，那么就会影响后面的结果。所以子数组需要重新开始。
            // 注意，这里设置0，表明不会影响每个元素值。
            if (sums <= 0) {
                sums = 0;
            }
        }

        return max;
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0095_03 s = new Solution_0095_03();

        int[] nums = {-5, -3, -9, -6, -1};
        System.out.println(s.maxSubArray(nums));
    }
}