Skip to main content

1 / 4思路

Maximum Subarray

原题

思路​

Kadane 算法:current 表示“以当前元素结尾的最大子数组和”。如果 current 变成负数,加上后面的元素只会更小,于是从当前元素重新开始。best 记录全局最大值。

复杂度​

  • 时间 O(n):一次遍历。
  • 空间 O(1):只维护两个变量。

代码​

def max_sub_array(nums: list[int]) -> int:
current = best = nums[0]
for value in nums[1:]:
current = max(value, current + value)
best = max(best, current)
return best

边界​

  • 全为负数:返回最大的单个元素,不能返回 0。
  • 只有一个元素:直接返回它。
  • 空数组:题目保证非空;工程代码应显式处理。