题目链接：点击这里

1.动态规划

令状态 $dp[i]$ 表示以 $A[i]$ 作为末尾的连续序列的最大和（即 $A[i]$ 必须作为连续序列的末尾）

通过这个 $dp[\ ]$ 数组，要求的最大子序和其实就是 $dp[0]，dp[1]，……，dp[n-1]$ 中的最大值。

现作如下考虑：因为 $dp[i]$ 要求是必须以 $A[i]$ 结尾的连续序列，那么只有两种情况：

这个最大和的连续序列只有一个元素，即以 $A[i]$ 开始，以 $A[i]$ 结尾。
这个最大和的连续序列有多个元素，即从前面某处 $A[p]$ 开始 $(p<i)$ ，一直到 $A[i]$ 结尾。

对第1种情况，最大和就是 $A[i]$ 本身。

对第2种情况，最大和是 $dp[i-1] + A[i]$ ，即 $A[p]+...+A[i-1] + A[i] = dp[i-1] + A[i]$ 。

于是得到状态转移方程： $dp[i] = max\left\{A[i], \ dp[i-1]+A[i]\right\}$ ，其中 $dp[0] = A[0]$

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

AC代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);

        dp[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
            if(dp[i - 1] > 0)   dp[i] = dp[i - 1] + nums[i];
            else    dp[i] = nums[i];
        }
        
        // dp[i]存放以nums[i]结尾的连续序列的最大和，需要遍历得到最大的才是结果
        int ans = INT_MIN;
        for(int i = 0; i < n; i++)
            if(dp[i] > ans)
                ans = dp[i];

        return ans;
    }
};

/* 和上面思路完全一致，代码更加简洁：
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);

        dp[0] = nums[0];
        int ans = dp[0];
        for(int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ans = max(ans, dp[i]);
        }

        return ans;
    }
};
*/

空间优化：我们只需要一个变量 premax 保存前一个状态的最大值，另需一个变量 ans 保存全局最大值。

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

AC代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int premax = nums[0];
        int ans = nums[0];
        for(int i = 1; i < n; i++)
        {
            if(premax > 0)  premax = premax + nums[i];
            else    premax = nums[i];
            ans = max(ans, premax);
        }

        return ans;
    }
};

2.分治

最大连续子序列和主要由以下三部分子区间里元素的最大和，对它们三者求最大值即可。

image.png

由递归主定理 $T(n)=2T(n/2)+O(n)$ ，解出总时间复杂度为 $O(nlogn)$ 。

需要额外 $O(logn)$ 的空间用于递归的系统栈。

class Solution {
public:
    int calc(int l, int r, vector<int>& nums)
    {
        if(l == r)  return nums[l];

        int mid = (l + r) >> 1;

        int left = calc(l, mid, nums);
        int right = calc(mid + 1, r, nums);

        int lmax = nums[mid], lsum = 0;
        for(int i = mid; i >= l; i--)
        {
            lsum += nums[i];
            lmax = max(lmax, lsum);
        }

        int rmax = nums[mid + 1], rsum = 0;
        for(int i = mid + 1; i <= r; i++)
        {
            rsum += nums[i];
            rmax = max(rmax, rsum);
        }

        return max(max(left, right), lmax + rmax);
    }

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return calc(0, n - 1, nums);
    }
};

LeetCode 53. 最大子序和

LeetCode 53. 最大子序和

1.动态规划

2.分治