Python Kadane算法两个实现示例的效率对比及运算逻辑疑问

1. 两个实现的Pythonic程度与效率差异 #

两个实现的核心差异不止遍历方式，可从三个维度对比：

• 逻辑正确性差异：示例1存在边界缺陷，它的max_sum初始值设为0，如果输入数组全为负数，返回结果会是0而非数组中最大的负数，不符合最大子数组和的定义；示例2初始值均取数组第一个元素，没有这个逻辑问题。
• 遍历方式的开销差异：示例1用nums[1:]遍历会生成原数组的切片副本，当处理超大规模数组时，切片的内存复制开销会明显上升；示例2用range(1,size)遍历索引，Python3中range是惰性生成的迭代对象，不会产生额外的列表副本开销。不过如果示例1优化掉切片，改成直接遍历元素的写法，其实比索引遍历更符合Python的开发习惯。
• 接口设计差异：示例2要求调用方手动传入数组长度size，属于冗余设计，Python中函数内部可以直接调用len(a)获取长度，这种写法既不Pythonic还容易因传错参数出问题。

兼顾Pythonic和效率的优化版本参考：

def max_sub(nums):
    if not nums:
        return 0
    max_sum = so_far = nums[0]
    for x in nums[1:]:
        so_far = max(x, x + so_far)
        max_sum = max(so_far, max_sum)
    return max_sum

2. 运算逻辑理解方法 #

Kadane算法的核心逻辑非常简单：对数组中每一个元素，我们只需要计算「以这个元素为结尾的最大连续子数组和」，再在所有计算结果里取最大值即可。
而以当前元素结尾的最大子数组和只有两种可能：

• 前面的子数组和为负数，加进去反而更小，所以只取当前元素本身
• 前面的子数组和为正数，加进去更大，所以取前面的和加当前元素

对应你遇到的两个疑惑点解释：

• 示例1中so_far变为1的原因：初始so_far是第一个元素-2，遍历到第二个元素1时，执行so_far = max(1, 1 + (-2)) = max(1, -1)，所以取了更大的1，而非直接相加的-1。
• 示例2中max_sum从-2直接变为4的原因：初始max_so_far = curr_max = -2，遍历到第二个元素-3时，curr_max = max(-3, -2 + (-3)) = -3，max_so_far还是max(-2, -3) = -2；到第三个元素4时，curr_max = max(4, -3 + 4) = max(4,1) =4，再更新max_so_far = max(-2,4)=4，你是漏掉了第二个元素的运算步骤，才会误以为是-2+4计算得到的结果。

如果要更快理解，你可以拿小的测试用例，手动列出每一步的curr_max和max_sum的值，演算2-3次就能完全摸清逻辑。

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