python - 最大子数组总和 - 我的解决方案哪里错了？Kadane 算法

Question

这是问题的描述：

最大和子数组问题在于找到数组或整数列表中连续子序列的最大和：

max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) 应该是 6: [4, -1, 2, 1]

简单的情况是列表仅由正数组成并且最大和是整个数组的总和。如果列表仅由负数组成，则返回 0。

空列表被认为具有零最大和。请注意，空列表或数组也是有效的子列表/子数组。

到目前为止，我的解决方案是：

def max_sequence(arr):
sum = 0
max = 0
for i in arr:
    sum += i


    if i > max:
        max = i
        sum = max
        

    elif sum > max:
        max = sum
    
return(max)

它适用于简单的例子，但不适用于随机的例子......你能帮我在哪里犯了错误/我没有考虑什么吗？

Answer 1

这可能是另一种方法：

def consequtive_sub_lists(l): 
    sublists = []
    for iter, item in enumerate(l):
        sublists.append([item])
        cur_sublist = [item]
        for idx in range(iter+1, len(l)):
            cur_sublist.append(l[idx])
            sublists.append(cur_sublist.copy())
    return sublists
        
            
sublists = consequtive_sub_lists([1,2,-3,4])
max_sum, max_list = max([(sum(item), item) for item in sublists])
print(f"max_sum: {max_sum}")
print(f"max_list: {max_list}")

输出：

max_sum: 4
max_list: [4]

一些解释：我将解决方案分为两个主要步骤：

• 从给定列表中创建所有后续子列表（作为列表列表）
• 从中找出总和最大的元素

对于 Kadane 算法（使其类似于此处的解决方案）

def max_sequence(arr):
    max = 0
    sum = 0
    for i in arr:
        sum += i
        if sum > max:
            max = sum
        if sum < 0:
            sum = 0
        
    return max

这是工作