最大子数组和

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

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

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

分析

初步思考

这个题的关键就是找出最大和。例如[1,-2,3]此时最大和的连续子数组就是3本身，我们需要把前边的数全部丢掉。[1,-1,3]最大就是整个数组，我们遇到负数的时候不一定就把前边的全部抛弃掉。所以这个题的关键就变成了，我们何时丢掉前边的数组。

继续思考

• 前边的和是负数，后边的比前边的大，丢掉

好像就这一种情况，我们需要把前边的和给丢掉。接下来我们论证一下我们的猜测。

• 如果前边的和是负数，后边的数也是负数，但是如果比前边的大，都可以换成后边的数。例如[-3,-4,-1]，此时我们就取-1为最大连续子数组。
• 如果前边的和是负数，后边的数是负数，但是如果比前边的小，我们可以不管，继续相加，直到遇到比这个和大的数。例如[-3,-4,-1]中，前两个数相加即可。
• 如果前边的和是负数，后边的数是正数，比前边的数大，可以换成后边的数。例如[-3,-4,1]，此时我们就取1为最大连续子数组。
• 如果前边的和是正数，后边的数是正数，则继续相加。例如[3,4,1]中，相加即可。
• 如果前边的和是正数，后边的数是负数，则继续相加。例如[1,-1,3]中，相加即可。1+(-1)=0不是负数继续和后边3相加0+3还是3，能找出来最大子数组和。如果是[1,-2,1],1+(-2)=-1是负数，后边的数比前边的数大，取后边的数，所以最大子数组和是1。

所以这个题就很清晰了，就是判断前边相加的和是否是负数，如果是负数，再比较后边的数是否大于前边的和，如果大于，则将和重置为后边的这个数。其他情况一律相加即可。

答案

 public static int maxSubArray(int[] nums) {
        int maxResult = nums[0];
        int nowResult = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nowResult < 0 && nums[i] > nowResult) {
                nowResult = nums[i];
            } else {
                nowResult = nowResult + nums[i];
            }
            if (nowResult > maxResult) {
                maxResult = nowResult;
            }
        }
        return maxResult;
    }

标准答案是直接调用了Math类来进行的计算，看起来更简单明了，代码可读性更好，这里也贴上。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

复杂度

• 时间复杂度：O(n)，需要遍历一遍数组。
• 空间复杂度：O(1),需要两个变量记录，最大和和当前和。

总结

上边这个题看到本质，就很简单，就是找到上边的这个分界条件。先将最大和存储起来，用来和其他的和做对比，这种算法叫做动态规划法。看到标准答案还有另外一种答案叫分治法，使用了线段树。还真不会，改天专门学一学。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！