LeetCode 53. 最大子数组和

怎么说，看着简单，想的也简单，写到时候却想多了。30min才搞定。
刚开始写了个时间O(n²)的，想按顺序，固定好第一个，后边的位数就是不固定了，找出一个最大的，
然后把不同的第一个中的最大的比较出一个最大的,最后输出下标。坑了坑了。。。
却忘了，根本不需要这么多信息。只需要找出当前子串中最大的值就好。(刚开始还以为要输出下标。。。。)
没错，就这么简单。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int len = nums.size();
        int maxSum = nums[0],sum=0;
        for(int i=0;i<len;i++){
            sum = max(sum+nums[i],nums[i]);
            maxSum = max(maxSum,sum);
        }
        return maxSum;
    }
};

后边再想想O(n)的解法。