调试：最大和连续子数组

Question

我正在解决一个要求最大和连续子数组的问题。我知道这个问题可以通过使用 Kadane 的算法来解决，但我不知道该算法，所以我尝试自己编写问题代码。

这是我写的代码：

def maxSubarray(arr): # 'arr' is the list for which we have to calculate the maximum sum
    h1 = arr[0]
    h2 = arr[1]
    subset_sum = -sys.maxsize-1
    for i in range(1,len(arr)):
        h1 = max(h2,h1+arr[i])
        subset_sum = max(h1,subset_sum)
    subset_sum = max(max(arr),subset_sum) # This is used if all elements in the list are negative

但是这段代码没有给出正确的输出，我似乎无法弄清楚出了什么问题？谁能帮帮我？

Answer 1

您没有在每次迭代时更新 h2。

无需更新，您可以直接使用 arr[i] 来查找最大值。

def maxSubArray(self, arr: List[int]) -> int:
        h1 = arr[0]
        subset_sum = -sys.maxsize-1
        for i in range(1,len(arr)):
            h1 = max(arr[i],h1+arr[i])
            subset_sum = max(h1,subset_sum)
        subset_sum = max(max(arr),subset_sum)
        return subset_sum

调试：最大和连续子数组

Debugging: Largest Sum Contiguous Subarray

python

algorithm

data-structures

kadanes-algorithm