题目

53. 最大子数组和

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

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

1
2
3
4
5
6
7
8
9
10
11
12
示例 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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
};

image.png

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

代码2

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

这个思路也是一样，只不过将判断换到了当前位之后就处理了

  • 维护一个sum，作为当前子数组的和；
  • 每一次都让sum+=i，并更新最大值；
  • 如果当前sum小于等于0了，当前子数组的和+下一位肯定会小于下一位本身，此时置为0，从下一位开始重新计算一个新的子数组和；
  • 直到遍历完毕返回维护的最大值。

两个写法都能过，重点还是理解思路啦！

image.png

思路二：动态规划

说明

用动态规划的思路来思考这道题目，首先是确定dp数组的含义

  • dp[i]代表以i为结尾（包括i）的最大连续子数组和。

那么状态转移就有两种情况：

  1. 将当前元素计入子数组，即dp[i] = nums[i] + dp[i-1]；
  2. 从当前元素开始重新记录一个新的子数组，即只保留nums[i]；

我们用max函数选取这两个情况中的最大值就可以了。

从递推公式中可以得知，dp[i]依赖于dp[i-1]，所以需要初始化dp[0]，显然dp[0] = nums[0]，因为第一位元素开始的子数组只有他自己。

初始化完毕后，从下标1开始遍历nums数组就可以了。

代码

从这个代码能看出来，虽然我们是用了dp数组这种比较“标准”的方式来进行解题的，但它本质上和上文中使用的贪心算法没有特别大的区别。根本上的思路完全一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // i下标为结尾的最长连续子数组的最大和
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];      // 初始化
        int result = nums[0]; // 最大值
        for (int i = 1; i < nums.size(); i++) {
            // 判断是沿用当前的子数组，还是从当前位置新开一个子数组
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        return result;
    }
};

image.png

The end

这道题还有很多不同的解法，可以参考这个博客：连续子数组的最大和问题（五种解法）