给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
解析:
[-2,1,-3,4,-1,2,1,-5,4]
max = -2
tmp = 0
tmp = Math.max(1, 1);
max = 1
tmp = Math.max(1 + -3, -3);
max = 1
遍历数组。
遍历数组。
max记录当前最大子序列和。
更新tmp要么接续连续+新值,要么是新值。
(思想就是动态规划,来了新值,选择继续连续 还是 新值)
然后比较max与tmp值。
如果连续的结果/新值 tmp 结果变大了,就更新max = tmp。没变大,还是原来的max。
class Solution {
public int maxSubArray(int[] nums) {
int serial = 0, max = nums[0]; // 设置连续值为0,最大值默认为首个值。
for(int num : nums) { // 遍历数组
serial = Math.max(num, num + serial); // serial要么选择连续,要么选择新值
max = Math.max(max, serial); // 比较上个最大值与当前连续/新值哪个更大
}
return max;
}
}