只差一点点

这就是最好的时代

【LeetCode.剑指Offer.42】连续子数组的最大和

分类于

题目：连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为**O(n)**。

示例1:

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

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

分析：

我们用 f(i)代表以第i个数结尾的「连续子数组的最大和」

只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求f(i)呢？

我们可以考虑 nums[i] 单独成为一段还是加入f(i-1)对应的那一段，这取决于nums[i]和f(i−1) + nums[i] 的大小，我们希望获得一个比较大的

于是可以写出这样的动态规划转移方程：
f(i) = max{ f(i−1) + nums[i], nums[i] }

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = nums[0];
        int ret = nums[0];

        for (int i =  1; i < n; i++) {
            f[i] = max(f[i - 1] + nums[i], nums[i]);
            ret = max(f[i], ret);
        }
        return ret;
    }
};

时间复杂度O(n)，空间复杂度O(n)

改进：

由于 f[i] 只是与 f[i - 1] 和 nums[i] 有关，且 ret 只与当前的 f[i] 有关，不需要存储整个数组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int nowMax = 0;
        int ret = nums[0];
        for (auto x : nums) {
            nowMax = max(nowMax + x, x);
            ret = max(nowMax, ret);
        }
        return ret;
    }
};

时间复杂度O(n)，空间复杂度O(1)

细节：

1.只需求出最大值，不用求出最大的子数组