1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int m=nums[0],cur=nums[0];
 5         for(int i=1;i<nums.size();++i){
 6             cur=cur<0?nums[i]:cur+nums[i];
 7             m=max(m,cur);
 8         }
 9         return m;
10     }
11 };

 1 class Solution {
 2 public:
 3     /**
 4     *線段樹：分治，將一段序列分成左右兩段來求解。
 5     *lSum 表示 [l, r] 內以 l 為左端點的最大子段和。lSum=max(左段.lSum,左段.iSum+右段.lSum)
 6     *rSum 表示 [l, r] 內以 r 為右端點的最大子段和。rSum=max(右段.rSum,右段.iSum+左段.rSum)
 7     *iSum 表示 [l, r] 的區間和。iSum=左段.iSum+右段.iSum
 8     *mSum 表示 [l, r] 內的最大子段和。分三種情況，最大子序在左段中，在右段中，跨段。mSum=max(l.mSum,r.mSum,l.rSum+r.lSum)
 9     */
10     /*與動態規劃相比，時間復雜度相同，但是因為使用了遞歸，并且維護了四個信息的結構體，運行的時間略長，空間復雜度也不如動態規劃優秀，
11　　　　而且難以理解。那么這種方法存在的意義是什么呢？對于這道題而言，確實是如此的。但是仔細觀察分治法，它不僅可以解決區間 [0, n-1]，還可以用于
12　　　　解決任意的子區間 [l,r] 的問題。如果我們把 [0,n?1] 分治下去出現的所有子區間的信息都用堆式存儲的方式記憶化下來，即建成一顆真正的樹之后，
13　　　　我們就可以在O(logn) 的時間內求到任意區間內的答案，我們甚至可以修改序列中的值，做一些簡單的維護，之后仍然可以在O(logn) 的時間內求到任意
14　　　　區間內的答案，對于大規模查詢的情況下，這種方法的優勢便體現了出來。這棵樹就是神奇的數據結構——線段樹。*/
15     struct Status{
16         int lSum,rSum,iSum,mSum;
17     };
18     Status pushUp(Status l,Status r){
19         int lSum=max(l.lSum,l.iSum+r.lSum);
20         int rSum=max(r.rSum,r.iSum+l.rSum);
21         int iSum=l.iSum+r.iSum;
22         int mSum=max(max(l.mSum,r.mSum),l.rSum+r.lSum);
23         return (Status){lSum,rSum,iSum,mSum};
24     }
25     Status get(vector<int>& nums,int l,int r){
26         if(l==r)
27             return Status{nums[l],nums[l],nums[l],nums[l]};
28         int m=(l+r)>>1;
29         return pushUp(get(nums,l,m),get(nums,m+1,r));
30     }
31     int maxSubArray(vector<int>& nums) {
32         return get(nums,0,nums.size()-1).mSum;
33     }
34 };