LeetCode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

思路

这个是剑指Offer还是什么程序员面试经典或者是编程珠玑上的一道题，反正已经广为流传了。
O(n)复杂度的想法是，假定我有之前能得到的最大和子串的和sum[i-1]和当前值a[i]，如何得到当前的最大和sum[i]呢？分两个情况：

• 如果sum[i-1]+a[i]<a[i]，比如上面那个数列的前两项-2+1 = -1 < 1，那意思就是前面那么好的加起来还不如从我这边重新开始来的好，则sum[1]就是a[i]
• 否则，更新sum[i]=sum[i-1]+a[i]

概括成一句话就是，既然之前的人加在一起都不如我，那就我带头上吧！

代码

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