6

我很难理解我发现的 Kadane 算法的这两个示例中发生了什么。我是 Python 新手，我希望理解这个复杂的算法能帮助我更好地查看/阅读程序。

为什么一个例子比另一个更好，它只是List vs Range？是否还有其他东西可以使示例之一更有效？此外，还有一些关于计算中发生了什么的问题。（示例中的问题）

我使用PythonTutor来帮助我一步一步了解到底发生了什么。

示例 1：

在 PythonTuter 中，当您在提供的屏幕截图中选择下一步时，so_far 的值变为 1。这是怎么回事？给出总和，我认为它加上 -2 + 1 即 -1，所以当 so_far 变为 1 时，这是怎么回事？

        def max_sub(nums):
            max_sum = 0
            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
        
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    max_sub(nums)
                6

在此处输入图像描述

示例 2：

这一个类似的问题，当我选择 NEXT 步骤时，max_sum 从 -2 变为 4 ......但是如果它在 2 中添加元素（即 4）怎么办。对我来说，那将是 -2 + 4 = 2 ？

def maxSubArraySum(a,size):
     
    max_so_far =a[0]
    curr_max = a[0]
     
    for i in range(1,size):
        curr_max = max(a[i], curr_max + a[i])
        max_so_far = max(max_so_far,curr_max)
         
    return max_so_far
 
a = [-2, -3, 4, -1, -2, 1, 5, -3]
print("Maximum contiguous sum is" , maxSubArraySum(a,len(a)))
     Maximum contiguous sum is 7

在此处输入图像描述

所以，这将是一个两部分的问题，而不是：

[1]Based on understandings, why would one be more pythonic and more efficient than the other? 
[2]How can I better understand the calculations happening in the examples?
4

2 回答 2

1

只需观察每个步骤，您就可以解决这个问题： [Notes] 这个程序似乎是基于混合整数的假设工作的？只有正面和负面。

# starting
so_far  = -2   # init. to nums[0]
max_sum = 0

# in the for-loop:
x =  1         # starting with nums[1:]
so_far = max(1, -1)   -> 1   (x is 1, -2 + 1)
max_sum = max(0, 1)   -> 1
.....   continue .... each step is to find the max accumulated numbers sum, as it's evident in the max( ) statement.  *There is no `sum` involved, except it tried to determine the current x is good (not negative) then so add it to the so_far.
于 2021-08-31T18:53:54.807 回答
1

比较这两种不同方法的更多性能测量数据点表明，第一个示例肯定比输入大小为 2k 的第二个示例快约 22-24%。

if __name__ == '__main__':
    L = list(range(-1_000, 1_000, 1))
    random.shuffle(L)

    baseTestCase = partial(max_sub, nums=L)
    print(timeit.timeit(baseTestCase, number=100_000))  # 86.0588067
    
    rangeTestCase = partial(max_SubArraySum, a=L, size=len(L))
    print(timeit.timeit(rangeTestCase, number=100_000)) # 105.415955
于 2021-09-01T07:56:17.157 回答