1. 题目

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

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

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

2.1. 动态规划

动态规划入门题。

令dp[i]表示以第i个数结尾的连续子数组的最大和，即所求为 $\max\limits_{0\leq i\leq n-1}{dp[i]}$

转移方程为 $dp[i]=max(dp[i-1]+a[i],a[i])$

空间优化之后可以不用数组保存每一个dp[i]的值。

2.2. 线段树（分治）

线段树解决区间问题。

每个结点保存四个值，lSum，rSum，mSum，iSum：

lSum 表示 [l, r] 内以 l 为左端点的最大子段和

rSum 表示 [l, r] 内以 r 为右端点的最大子段和

mSum 表示 [l, r] 内的最大子段和

iSum 表示 [l, r] 的区间和

更新信息：

首先最好维护的是 iSum，区间 [l, r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。

对于 [l, r]的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。

对于 [l, r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。

当计算好上面的三个量之后，就很好计算 [l, r] 的 mSum 了。我们可以考虑 [l, r] 的 mSum 对应的区间是否跨越 mm——它可能不跨越 mm，也就是说 [l, r] 的 mSum 可能是「左子区间」的 mSum 和「右子区间」的 mSum 中的一个；它也可能跨越 mm，可能是「左子区间」的 rSum 和「右子区间」的 lSum 求和。三者取大。

3. 代码

3.1. 动态规划

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

3.2. 线段树

const int MAXN=1e4+5;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node{
    int lSum,rSum,mSum,iSum;//[l,r]  l为左端点的最大字段和、r为右端点的最大字段和、最大字段和、区间和 
}T[MAXN<<2];
void push_up(int p,int l,int r){
    int mid=(l+r)>>1;
    T[p].iSum=T[ls(p)].iSum+T[rs(p)].iSum;
    T[p].lSum=max(T[ls(p)].lSum,T[ls(p)].iSum+T[rs(p)].lSum);
    T[p].rSum=max(T[rs(p)].rSum,T[rs(p)].iSum+T[ls(p)].rSum);
    T[p].mSum=max(max(T[rs(p)].mSum,T[ls(p)].mSum),T[ls(p)].rSum+T[rs(p)].lSum);
}
void build(vector<int>&nums, int p,int l,int r){
    if(l==r){
        T[p].lSum=T[p].rSum=T[p].mSum=T[p].iSum=nums[l-1];
        return;
    }
    int mid=(l+r)>>1;
    build(nums,ls(p),l,mid);
    build(nums,rs(p),mid+1,r);
    push_up(p,l,r);
}
int query(int p,int l,int r,int nl,int nr){
    if(nl<=l&&nr>=r) return T[p].mSum;
    int res=-(1<<30),mid=(l+r)>>1;
    if(nl<=mid) res=max(res,query(ls(p),l,mid,nl,nr));
    else res=max(res,query(rs(p),mid+1,r,nl,nr));
    return res;
}
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        build(nums,1,1,n);
        return query(1,1,n,1,n);
    }
};

53 最大子序和