class Solution {public:    int maxSubArray(vector
      
       & nums) {        int pre=nums[0];        //int now;        int maxSum=nums[0];                for(int i=1;i
       
        0){                pre+=nums[i];                            }            else{                pre=nums[i];            }            if(pre>maxSum){                maxSum=pre;            }        }                return maxSum;            }};
       
      

如果之前的和大于0，那么加上它。否则，舍弃，pre为当前数。

如果加了之后比已知的最大和大，那么最大和是加了之后的和。

……我也忘了怎么想出来的。

 动态规划嘛，从1到n。找出i+1相对于i的变化。

如果前面的和 < 0，前面没有。

大于0，那么好，加上。

最大和用maxSum保存，然后比较加上是否比它大。

 

---

 

还可以用分治，O(nlogn)