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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分享一段我认为简单易懂的代码

class Solution {

public:

 int maxSubArray(vector& nums) {

        int sum = 0;

        int result = nums[0];

        for(int i = 0; i < nums.size(); i++) {

            sum += nums[i];

            result = max(sum, result);

            sum = max(sum, 0);         

        }

        return result;

    }

};

认为这段代码很棒，一开始无法确定subarray的起始点在哪里，代码里可以了解到，我们首先初始化结果为 nums[0], 

之后如果有max + nums[i] > max 的，那么该数一定大于0，那么sum = max（sum，0）中sum就可以持续对下一个数计算总和

如果之后 0< max + nums[i] < max 的，那么sum可以继续计算下一个，防止类似 4， -2，99，1 后面有正整数出现

如果之后 max + nums[i] < max 且 max + nums[i] < 0 的，sum清零，result在这一组合中已经出结果，sum又要从一个全新的位置开始算和

随后，result再开始像之前那样的变化