最大子数组和：为何我的代码耗时过长甚至无法运行？

你的代码处理小型列表时能正常运行，但遇到元素数量超过100的大型列表就耗时极长甚至无法运行，核心问题出在时间复杂度太高。

原代码问题分析 #

你当前的实现用了两层嵌套循环：

def max_sequence(arr):
    length = len(arr)
    if length == 0:
        return 0
    if all(i < 0 for i in arr) == True:
        return 0
    max_num = 0
    sum_num = 0
    for i in range(length):
        sum_num = 0
        for j in range(i,length):
            sum_num += arr[j]
            if sum_num > max_num:
                max_num = sum_num
    return max_num

这种写法的时间复杂度是O(n²)，n是列表元素的数量。当n=100时，循环执行次数是5050次；n=1000时，次数会涨到500500次；n=10000时直接变成50005000次——计算量呈平方级增长，自然会导致耗时剧增甚至卡住。

优化方案：使用Kadane算法 #

可以用时间复杂度为**O(n)**的Kadane算法（卡登算法），只需要一次遍历就能找到最大子数组和，完美解决大型列表的性能问题。优化后的代码如下：

def max_sequence(arr):
    if not arr:
        return 0
    # 检查是否全为负数
    if all(num < 0 for num in arr):
        return 0
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        # 选择从当前元素重新开始，或者延续之前的子数组
        current_sum = max(num, current_sum + num)
        # 更新最大和
        max_sum = max(max_sum, current_sum)
    # 确保返回值不小于0（和原逻辑一致）
    return max(max_sum, 0)

逻辑说明：

• 遍历数组时，current_sum始终记录当前子数组的最大和：如果加上当前元素后的和比当前元素本身小，就从当前元素重新开始计算子数组和。
• max_sum全程跟踪遍历过程中出现过的最大子数组和。
• 保留了原代码中"空数组返回0"、"全负数返回0"的逻辑。

内容的提问来源于stack exchange，提问作者Amin