难度: Easy
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
Submission
运行时间: 27 ms
内存: 16.8 MB
from typing import List class Solution: def maxSubArray(self, nums: List[int]) -> int: prefix = nums[0] ans = nums[0] for i in range(1, len(nums)): if prefix < 0: prefix = nums[i] else: prefix += nums[i] ans = max(ans, prefix) return ans
Explain
题解采用了Kadane算法解决问题。算法的核心思想是通过遍历数组，维护一个当前连续子数组的最大和(prefix)以及全局的最大和(ans)。对于数组中的每个元素，算法检查当前连续子数组的和(prefix)是否为负数：如果是负数，表示加上当前元素后不可能使得子数组和增大，因此重新开始计算新的子数组和，即将prefix重置为当前元素的值；如果不是负数，将当前元素加到prefix上。同时，使用ans记录下遍历过程中遇到的最大的prefix值。
时间复杂度: O(n)
空间复杂度: O(1)
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
prefix = nums[0] # 初始化prefix为数组的第一个元素
ans = nums[0] # 初始化ans为数组的第一个元素，用来记录最大子数组和
for i in range(1, len(nums)):
if prefix < 0:
prefix = nums[i] # 如果当前prefix为负，重置prefix为当前元素
else:
prefix += nums[i] # 否则加上当前元素，尝试增加子数组和
ans = max(ans, prefix) # 更新全局最大子数组和
return ans # 返回最大子数组和
Explore
在Kadane算法中，如果当前子数组的和(prefix)为负数，意味着它对于形成可能的更大子数组和没有正面贡献。即便是后续元素具有较大正值，前面的负数和也会拖低总和。因此，将prefix重置为当前元素的值是为了丢弃前面的负数和，从当前元素重新开始计算新的子数组和，尝试寻找一个新的、可能更优的子数组起点。这种做法的理论依据在于，任何包含前面负和的子数组都不可能是最优子数组，因此从新的位置开始搜索更有可能达到更高的子数组和。
即使数组中所有元素都是负数，Kadane算法仍然有效。在这种情况下，算法会找到最小的负数并将其作为最大的子数组和。这是因为每次迭代都会比较当前元素和当前子数组和(prefix)，即使所有数字都是负的，算法也会通过这种方式找到其中最大（或者说最不负）的一个值，这个值将是所有负数中最接近于零的数，即为最大子数组和。
在Kadane算法的实现中，全局最大子数组和(ans)在每次数组的元素被迭代处理时都会更新。每次迭代，算法会计算当前的子数组和(prefix)，然后使用ans记录下这个过程中遇到的最大的prefix值。确切地说，每次迭代过程中，都会用`ans = max(ans, prefix)`进行比较和更新，确保ans始终保留最大的子数组和。这种每步都更新的策略可以确保不遗漏任何可能成为最大子数组的连续段。