【每日一题】最大子数组和

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：动态规划
- 方法二：分治
- 方法三：前缀和
写在最后

Tag

【动态规划】【前缀和】【数组】【2023-11-20】

题目来源

53. 最大子数组和

题目解读

找出数组 nums 中连续子数组元素和的最大值。数组中的元素范围为 $10^4, 10^4]$ ，数组长度最大为 $10^5$ 。

进阶：如果你已经成功实现了时间复杂度为 $O (n)$ 的解法，尝试使用更为精妙的 分治法 求解。

解题思路

方法一：动态规划

状态

dp[i] 表示以第 i 个数结尾的连续子数组的最大和，最后返回的结果为：

$max_{0<=i<=n-1}{dp[i]}$

转移关系

以第 i 个数结尾的连续子数组的最大和有这样的转移关系：

$d p [i] = ma x (d p [i - 1] + n u m s [i], n u m s [i])$

base case

由于以第 i 个数结尾的连续子数组的最大和只和上一个状态有关，因此可以使用一个变量 prev 来维护上一个转态的最大子数组和，这样就可以将时间复杂度降低到 O(1)。

初始化 prev = 0，res = nums[0]（表示本次状态的最大值）。

最后返回

最后返回 res。

实现代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int prev = 0, res = nums[0];
        for (int num : nums) {
            prev = max(prev + num, num);
            res = max(res, prev);
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O (n)$ 。

空间复杂度： $O (1)$ 。

方法二：分治

方法二的计算思想类似于线段树，实质上是分治思想的应用。在线段树中我们可以维护一个区间上的最大元素值、最小元素值以及元素和。本题中使用分治思想解决，我们首先需要解决维护区间上什么样的数据结构。

对于一个区间 [l, r]，我们维护四个变量：

lSum：表示 [l, r] 内以 l 为左端点的最大子数组和；
rSum：表示 [l, r] 内以 r 为右端点的最大子数组和；
mSum：表示 [l, r] 内最大子数组和；
iSum：表示 [l, r] 的区间和。

区间 [l, r] 上四个变量如何更新呢？

iSum 等于左子区间的 lSum 加上右子区间的 rSum，即 iSum = lSum + rSum；
区间 [l, r] 上的 lSum 要么等于左子区间 [l, m] 的 lSum，要么等于左子区间 [l, m] 的 iSum 加上右子区间 lSum，二者取较大值；
同理，区间 [l, r] 上的 rSum 要么等于右子区间 [m+1, r] 的 rSum，要么等于右子区间 [m+1, r] 的 rSum 加上左子区间 rSum，二者取较大值；
当计算好上面的三个量之后，就很好计算 [l,r] 的 mSum 了。我们可以考虑 [l,r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l,r] 的 mSum 可能是「左子区间」的 mSum 和「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和「右子区间」的 lSum 求和。三者取最大值。

实现代码

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status){lSum, rSum, mSum, iSum};
    }

    Status get(vector<int>&a, int l, int r) {
        if (l == r) {
            return (Status){a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m+1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

复杂度分析

时间复杂度：渐进的时间复杂度为 $O (n)$ 。

空间复杂度：递归会使用栈空间，空间复杂度为 $O (l o g n)$ 。

方法三：前缀和

还可以使用前缀和的方法来解决。

我们在遍历数组 nums 时，设当前遍历的元素为 num：

更新前缀和 preSum += num；
最大子数组和等于当前前缀和减去上次更新的最小前缀和，即 res = max(res, preSum - minPreSum)；
更新最小前缀和 minPreSum = min(minPreSum, preSum)。

实现代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int preSum = 0, minPreSum = 0;
        int res = INT_MIN;
        for (int num : nums) {
            preSum += num;
            res = max(res, preSum - minPreSum);
            minPreSum = min(minPreSum, preSum);
        }
        return res;
    }
};