Leetcode热题Hot100-动态规划

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

假设 nums 数组的长度是 n，下标从 0 到 n−1。

我们用 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]}

不难给出一个时间复杂度 O(n)、空间复杂度O(n) 的实现，即用一个 f 数组来保存 f(i) 的值，用一个循环求出所有 f(i)。考虑到 f(i) 只和 f(i−1) 相关，于是我们可以只用一个变量 pre 来维护对于当前f(i) 的 f(i−1) 的值是多少，从而让空间复杂度降低到O(1)，这有点类似「滚动数组」的思想。

class Solution {
public:
    int maxSubArray(vector& nums) {
        int pre=0,maxAns=nums[0];
        for(const auto & x:nums) //作用就是迭代容器中所有的元素，每一个元素的临时名字就是x，等同于下边代码for (vector::iterator iter = nums.begin(); iter != nums.end(); iter++)
        {
            pre=max(pre+x,x);
            maxAns=max(maxAns,pre);
        }
        return maxAns;
}
};

1. 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
2. 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

这个分治方法类似于「线段树求解最长公共上升子序列问题」的 pushUp 操作。

我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l,r] 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l,r]，我们取m= 2/l+r，对区间 [l,m] 和 [m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。

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 &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& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

1. 假设序列 aa 的长度为 nn。时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为 O(logn)，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是 O(n)，故渐进时间复杂度为 O(n)。
2. 空间复杂度：递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(logn)。

​