最大子数组和问题：我的Kadane算法实现存在何种错误？

让我看看你的代码哪里出问题了——你的思路其实接近经典的Kadane算法，但有几个关键逻辑错误，导致在部分随机测试案例里失效。

主要错误点 #

1. 错误的sum重置条件 #

你当前只在当前元素i大于当前max时才重置sum为i，但正确的逻辑应该是：当累加后的sum变为负数时，就把sum重置为0。因为如果当前的累加和是负数，继续带着它加后面的元素只会拉低后续的总和，不如从下一个元素重新开始累加。

比如测试案例[1,2,-10,3,4]，你的代码处理到-10后sum变成-7，之后加3得到-4、加4得到0，这时你会因为i=4大于当前max（3）而把max设为4，但实际上3+4的和7才是正确的最大子数组和。如果在sum变成-7时重置为0，后续加3得到3、加4得到7，就能正确更新max到7。

2. 逻辑分支的顺序问题 #

你先执行sum += i再判断条件，这会导致一些不必要的错误计算。比如当当前元素是正数，但之前的sum是负数时，你先把正数加到负数sum里，再通过i > max的条件重置sum，虽然结果可能对，但过程绕了弯路，且容易在复杂案例中出错。

修正后的实现（符合题目要求） #

基于经典Kadane算法调整，完美适配题目中的特殊情况：

def max_sequence(arr):
    current_sum = 0
    max_sum = 0
    for num in arr:
        # 要么从当前数重新开始累加，要么继续累加当前数
        current_sum = max(num, current_sum + num)
        # 更新最大和记录
        max_sum = max(max_sum, current_sum)
    # 全负数/空数组时返回0，否则返回最大和
    return max_sum if max_sum >= 0 else 0

代码解释 #

• current_sum：记录当前正在累加的子数组和，每次选择从当前元素重新开始（如果当前元素比累加后的和更大，说明之前的累加是负数），或者继续累加当前元素。
• max_sum：遍历过程中持续记录遇到的最大子数组和。
• 最终判断：如果max_sum是负数（说明数组全为负数），返回0；否则返回max_sum，完美适配题目中的所有特殊规则。

测试验证 #

• 测试案例[-2, 1, -3, 4, -1, 2, 1, -5, 4]：返回6，正确。
• 测试案例[1,2,-10,3,4]：返回7，正确。
• 全负数数组[-5,-3,-1]：返回0，正确。
• 空数组[]：返回0，正确。
• 全正数数组[1,2,3]：返回6，正确。

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