目录

题目链接

注意点

• 最大值有可能是正负数交替着出现

解法

解法一：一次遍历即可。当sum小于0的时候就重新开始求和，因为sum小于0再加上一个数字绝对不可能是max(即sum+nums[i] < nums[i])时间复杂度为O(n)

class Solution {public:    int maxSubArray(vector
    
     & nums) {        int max = nums[0],sum = nums[0],i,n = nums.size();        for(i = 1;i < n;i++)        {            if(sum < 0)  // when sum < 0, sum + nums[i] < nums[i]            {                sum = nums[i];            }            else            {                sum += nums[i];               }            if(sum > max)            {                max = sum;            }        }        return max;    }};
    

小结

• 这道题有更多的解法，但是O(n)应该是最快的了。想起来这个还是我大一的时候从ACM培训讲座上学到的