动态规划或线段树：最大子序和（leetcode）

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

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

方法一：动态规划

 

 代码：

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

方法二：线段树

 

 代码：

class Solution {
public:
    /**
    *线段树：分治，将一段序列分成左右两段来求解。
    *lSum 表示 [l, r] 内以 l 为左端点的最大子段和。lSum=max(左段.lSum,左段.iSum+右段.lSum)
    *rSum 表示 [l, r] 内以 r 为右端点的最大子段和。rSum=max(右段.rSum,右段.iSum+左段.rSum)
    *iSum 表示 [l, r] 的区间和。iSum=左段.iSum+右段.iSum
    *mSum 表示 [l, r] 内的最大子段和。分三种情况，最大子序在左段中，在右段中，跨段。mSum=max(l.mSum,r.mSum,l.rSum+r.lSum)
    */
    /*与动态规划相比，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如动态规划优秀，
11　　　　而且难以理解。那么这种方法存在的意义是什么呢？对于这道题而言，确实是如此的。但是仔细观察分治法，它不仅可以解决区间 [0, n-1]，还可以用于
12　　　　解决任意的子区间 [l,r] 的问题。如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一颗真正的树之后，
13　　　　我们就可以在O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在O(logn) 的时间内求到任意
14　　　　区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是神奇的数据结构——线段树。*/
    struct Status{
        int lSum,rSum,iSum,mSum;
    };
    Status pushUp(Status l,Status r){
        int lSum=max(l.lSum,l.iSum+r.lSum);
        int rSum=max(r.rSum,r.iSum+l.rSum);
        int iSum=l.iSum+r.iSum;
        int mSum=max(max(l.mSum,r.mSum),l.rSum+r.lSum);
        return (Status){lSum,rSum,iSum,mSum};
    }
    Status get(vector<int>& nums,int l,int r){
        if(l==r)
            return Status{nums[l],nums[l],nums[l],nums[l]};
        int m=(l+r)>>1;
        return pushUp(get(nums,l,m),get(nums,m+1,r));
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums,0,nums.size()-1).mSum;
    }
};