为什么我的“最大邻接子数组和”解决方案不能适用于所有输入？

Question

对于上下文，这是codewars中的problem语句：problem语句

它本质上是一个经典的“查找最大子数组和”问题，尽管增加了一个重要的细节，即给定一个包含所有负数的数组，应该返回一个“0”，而不仅仅是最大的负数值。

首先，我充分意识到这个解决方案不是一个非常好或有效的解决方案。话虽如此，逻辑对我来说仍然是有意义的，所以我不太明白为什么它适用于某些输入而不是其他输入。我不能提供这个程序无效的输入，因为测试用例隐藏在代码战中。

我尝试使用以下示例运行代码；

• [1,0,2,-3,6]（应返回6)
• [-2,1,-3,4,-1,2,1,-5,4]（应返回6)
• [-2,-3,4,-1,5,1,5,-3]（应返回14）
• 等。他们都工作得很好

再说一遍，我只想知道为什么这个代码是不正确的背后的逻辑。我不是在寻找一个正确的替代解决方案（我现在已经意识到Kadane算法的存在）。这是我第一次盲目地尝试解决这个问题，所以我真的很想知道我做错了什么，这样我就可以从中吸取教训。

def max_sequence(arr):
    max_sum = 0
    max_subarr_index = 0
    for i, val in enumerate(arr):
        max_sum = max(max_sum, sum(arr[max_subarr_index:i+1]), val)
        if max_sum == val:
            max_subarr_index = i
    return max_sum

Answer 1

该漏洞存在于max_sum在算法中有双重用法。它习惯于：

>

保持到目前为止搜索的数组中找到的最大和

更新MAX_SUBARR_INDEX，如果较大的数组直接从索引I开始，而不是MAX_SUBARR_INDEX

对于第一点，您的算法工作得很好。其次，它失败了，因为max_sum不需要与当前所查看的子数组有任何关系。例如：

arr = [3, -4, 1, 1, ...]

现在对于i=3，变量如下所示：

max_sum = 3
max_subarr_index = 0

即。算法仍然“认为”最大子数组从索引0开始，其和为3。但是，以索引3结尾的最大子数组实际上是[1,1]，max_subarr_index=2。即。实际上有两个最大的子数组：

• 全局([3]表示i=3)
• 在当前索引处结束的最大和子数组([1,1]对于i=3)

您可以通过仅根据val和sum(arr[max_subarr_index:i+1]))的最大值更新max_subarr_index:

def max_sequence(arr):
    max_sum = 0
    max_subarr_index = 0
    for i, val in enumerate(arr):
        # update max_subarr_index based on sum of "current" max subarray
        tmp = max(sum(arr[max_subarr_index:i+1]), val)
        if tmp == val:
            max_subarr_index = i

        # global maximum found so far
        max_sum = max(max_sum, tmp)
        
    return max_sum