53. 最大子数组和

53. 最大子数组和

• 1 <= nums.length <= 105

• 104 <= nums[i] <= 104

解题步骤

1. 初始化：

• 设置结果变量 res 为最小整数值

• 设置当前子数组和 t 为0

• 设置遍历指针 i 和子数组起始位置 j

1. 遍历数组：

• 累加当前元素到子数组和 t

• 更新最大子数组和 res，取 res 和 t 的较大值

• 如果当前子数组和小于等于0，重置子数组：
• 将起始位置 j 移动到下一个位置
• 重置子数组和 t 为0

1. 返回最终的最大子数组和 res

算法思路解析

• 如果当前子数组和为负数，那么它对后面的子数组和只会产生负面影响，因此可以直接舍弃，从下一个元素重新开始计算

• 如果当前子数组和为正数，即使后面有负数，只要总和还是正的，就可以继续累加

• 通过不断更新 res，我们能够在遍历过程中记录下最大的子数组和

时间复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组。

• 空间复杂度：O(1)，只使用了常数个变量。

举例说明

• 遍历到 -2：t = -2，res = -2，由于 t ≤ 0，重置 t = 0

• 遍历到 1：t = 1，res = 1

• 遍历到 -3：t = -2，res = 1，由于 t ≤ 0，重置 t = 0

• 遍历到 4：t = 4，res = 4

• 遍历到 -1：t = 3，res = 4

• 遍历到 2：t = 5，res = 5

• 遍历到 1：t = 6，res = 6

• 遍历到 -5：t = 1，res = 6

• 遍历到 4：t = 5，res = 6