LeetCode 53. 最大子序和
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
解题思路:
实现局部最大推导出来全局最大的子序和
从代码角度上来讲:遍历 nums,从头开始用 count 累积,然后计算出当前count和result的最大赋值给result,如果 count 一旦加上 nums[i]变为负数,那么就应该从 nums[i+1]开始从 0 累积 count 了,因为已经变为负数的 count,只会拖累总和。
那么如何切换区间呢?
代码实现:
方法一:
这种方法的关键在于使用 count
变量来记录当前的连续子数组和,并随时更新最大和 result
。当 count
变为负数时,将其重置为 0 的目的是舍弃之前的负数和,重新从下一个元素开始计算连续子数组和。
这段代码的时间复杂度为 O(n),其中 n 是数组的长度。通过一次遍历数组,即可找到最大和的连续子数组。
方法二:
代码跟踪:
当输入数组为 [-2, 1, -3, 4, -1, 2, 1, -5, 4]
时,我们可以使用表格来清晰地展示每一步的计算过程。下面是一个示例:
根据上面的计算过程,最大和为6。
评论区