数组中连续子数组的最大和(LeetCode53. 最大子序和)

题目

解析

时间复杂为O(n)的算法。遍历数组的每个元素，记录当前元素的加和结果sum，和记录遍历到当前元素的最大和result。假设当前数组nums，遍历到下标为i的元素上，如果之前的sum值小于0，sum设为nums[i]，因为与负值相加只会让结果更小。sum大于等于0时，sum设为sum与nums[i]的和，这时的结果会更大。比较sum值和result值，如果sum更大，更新result记录下这个更大的值。

代码

public int maxSubArray(int[] nums) {
    int result = nums[0]; int sum = nums[0];
    for(int i = 1; i < nums.length; ++i){
        if(sum < 0){
            sum = nums[i];
        } else {
            sum = sum + nums[i];
        }
        if(sum > result){
            result = sum;
        }
    }
    return result;
}