如何找到数组中的最大连续负和？

Question

计算数组中任何一组连续索引的最大负和的最有效方法是什么？您可以采用数组中任何连续的正整数和负整数组来创建尽可能负的和。

例如，您有 arr = [10, -15, 2, 25, -16, -53, 22, 2, 1, -3, 60] 从 -16 和 -53 求和得到的最大负和是 -69。

另一个例子，你有 arr = [10, -15, -2, 10, -16, -53, 22, 2, 1, -3, 60] 最负的总和是 -76 来自 -15、-2、10、-16、-53 的总和。

Answer 1

你可以使用标准的Kadane’s algorithm，只是改变数组元素的符号。

def kadane(arr):
    max_so_far = float('-inf')
    max_ending_here = 0

    for i in range(0, len(arr)):
        arr[i] = arr[i] * -1
        max_ending_here = max_ending_here + arr[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here

        if max_ending_here < 0:
            max_ending_here = 0
    return max_so_far


print(kadane(arr=[10, -15, 2, 25, -16, -53, 22, 2, 1, -3, 60]) * -1)  # -69
print(kadane(arr=[10, -15, -2, 10, -16, -53, 22, 2, 1, -3, 60]) * -1) # -76

如何找到数组中的最大连续负和？

How to find the maximum consecutive, negative sum in an array?

python

arrays

algorithm

time-complexity