LeetCode题解：最大子数组和

题目描述

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例

• 示例1
  输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  输出：6
  解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
• 示例2
  输入：nums = [1]
  输出：1

思路方法

初始化pre为前面的数相加，只要前面的值为正数就一直相加，遇到负数pre将从当前节点值重新相加计算。（如此说明，有点难懂，可以按照代码试验一下就能明白）
同时最大值maxVal每次遍历不断更新。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0,maxVal = nums[0];
        for(int val:nums){
            //前一个数与该数相加为正，则相加，同时该值更新为和，
            pre = Math.max(pre+val,val);
            maxVal = Math.max(maxVal,pre);
        }
        return maxVal;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中n为nums数组的长度。我们只需要编译一遍数组便可得到答案。
• 空间复杂度：O(1)。常数空间若干变量。