【leetcode】53.最大子数组和

题目

53. 最大子数组和

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

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

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

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

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

思路

最简单的方式可以用一个三层的嵌套遍历找到这个最大值，时间复杂度是O(N^3)。但这样写肯定是不好的。

题目要求的是一个连续子数组的和，我们可以认为遍历到某一个数的时候，这个子数组的和就是到前一位的子数组和+当前值，这时候就会出现两种情况

前一位的数组和+当前值 < 当前值，这说明前一位的子数组和是一个负数，那还不如当前值自己大，所以直接选用当前值作为新一轮子数组的开始。
前一位的数组和+当前值 >= 当前值，可以将当前值算到前一位的这个子数组中，继续扩张。

每一次操作之后都需要更新最大和。

我们可以另外开辟一个数组来存放每一位的最大子数组和，再通过下标访问前一位的数组和。但实际上每一次遍历只和前一位的子数组和有关系，所以直接用int来存放前一位的子数组和就够了，不需要额外开辟数组的空间复杂度消耗了。

代码

代码1

代码比较简单，理解了思路就能写出来

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int prev = 0;         // 之前的最大子数组和，初始值0
        int maxNum = nums[0]; // 从数组中选一个值
        for (auto& i : nums) {
            // 如果之前的最大子数组和还没有我自己大，则从我自己开始新列一个子数组
            prev = max(prev + i, i);
            // 更新最大值
            maxNum = max(maxNum, prev);
        }
        return maxNum;
    }
};

时间复杂度O(N)，空间复杂度O(1)；

代码2

上面这个代码乍一看可能不好理解，我们可以按下面的方式写

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ret = INT32_MIN;
        int sum = 0;
        for (auto& i : nums) {
            sum += i;
            // 更新最大值
            if (sum > ret) {
                ret = sum;
            }
            // 如果当前sum为负数，那么需要重新开子数组了
            // 因为当前的sum加上下一位后，肯定没有下一位本身大！
            if (sum <= 0) {
                sum = 0; // 重置为0
            }
        }
        return ret;
    }
};