时间戳

首页 > 解决方案 > 为什么我的“最大连续子数组和”解决方案不适用于所有输入？

python - 为什么我的“最大连续子数组和”解决方案不适用于所有输入？

问题描述

对于上下文，这是 Codewars 中的问题陈述： 问题陈述

它本质上是经典的“查找最大子数组和”问题，尽管重要的附加细节是在给定所有负数的数组的情况下应该返回“0”，而不仅仅是最大的负数。

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

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

同样，我只想知道为什么这段代码不正确背后的逻辑。我不是在寻找正确的替代解决方案（我现在已经知道 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

标签： pythonalgorithm

解决方案

缺陷在于max_sum您的算法具有双重用途。它用于：

  1. 在迄今为止探索的数组上保持最大找到的总和

  2. 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]for i = 3）
  • 以当前索引结束的最大和子数组（[1, 1]for i = 3）

max_subarr_index您可以通过仅根据val和的最大值进行更新来解决此问题sum(arr[max_subarr_index:i+1])：

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

推荐阅读