题目
解析
时间复杂为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;
}
网友评论