连续子数组最大和Python算法超时求助（附低效实现代码）

看起来你遇到了经典的最大子数组和问题超时的情况——你的代码逻辑是对的，但三重循环的效率实在太低了，完全扛不住N=1e5的规模。让我帮你拆解问题并给出优化方案：

原代码的问题分析 #

你的代码通过枚举所有可能的连续子数组长度，再枚举每个长度对应的起始位置，最后逐个累加计算子数组和，这是三重嵌套循环，时间复杂度达到了O(n³)。当N=1e5时，这个运算量是1e15级别，远远超过了200毫秒能处理的范围（一般来说，Python每秒大概能处理1e6次运算），超时是必然的结果。

优化方案：Kadane算法（动态规划） #

我们可以用Kadane算法，只需要一次遍历数组就能解决问题，时间复杂度降到O(n)，完全符合题目要求的时间限制。

算法思路 #

1. 维护两个变量：
   • current_max：表示以当前元素结尾的连续子数组的最大和
   • global_max：表示遍历到当前位置时，全局的最大子数组和
2. 遍历数组时，对每个元素做两个选择：要么把它加入之前的子数组，要么从它开始新的子数组，即 current_max = max(num, current_max + num)
3. 每次更新current_max后，同步更新global_max，确保它始终是目前找到的最大值
4. 最后，如果global_max是负数（说明所有子数组和都是负的），就返回0，否则返回global_max

优化后的Python代码 #

n = int(input())
nums = list(map(int, input().split()))

# 初始化当前最大和与全局最大和为第一个元素
current_max = global_max = nums[0]

# 从第二个元素开始遍历
for num in nums[1:]:
    current_max = max(num, current_max + num)
    global_max = max(global_max, current_max)

# 按照题目要求，全负的情况返回0
print(max(global_max, 0))

测试示例验证 #

举几个例子看看效果：

• 示例1：

  输入：
  5
  1 -2 3 4 -5
  输出：7（对应子数组[3,4]）

• 示例2：

  输入：
  3
  -1 -2 -3
  输出：0（全负取0）

• 示例3：

  输入：
  4
  2 -1 2 3
  输出：6（对应子数组[2,-1,2,3]）

这个代码在N=1e5的情况下，只需要一次遍历，运行时间绝对不会超过200毫秒，完美解决超时问题。

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