题目描述：
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
题解：复杂度要求O(n)，则需要一次遍历解决。我们可以想到，如果连续子数组的和，即代码中sum小于等于0，则可以将数据元素直接赋值给sum，同时定义结果res，如果sum大于res，则赋值给res。
class Solution {
int res=Integer.MIN_VALUE;
int sum=0;
public int maxSubArray(int[] nums) {
for(int i=0;i<nums.length;i++){
if(sum<=0){
sum=nums[i];
}else{
sum+=nums[i];
}
if(sum>res){
res=sum;
}
}
return res;
}
}
这种方法通过一次遍历解决问题，复杂度也控制在了O(n)，但仍然可以进行优化，使代码更简洁
public int maxSubArray2(int[] nums) { int res=nums[0]; for(int i=1;i<nums.length;i++){ nums[i]+=Math.max(nums[i-1], 0); res=Math.max(res, nums[i]); } return res; }
这两种方法执行效率相同，但是第二种看起来更加简洁
原文：https://www.cnblogs.com/blosjin/p/13344412.html