CODEWITHSUNDEEP
pythonarraysalgorithmtime-complexity
Danny M
Danny M

Reputation: 85

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

What is the most efficient way to calculate the most negative sum for any set of consecutive indexes in an array? You can take any consecutive group of positive and negative integers in an array to create the most negative sum possible.

For example you have arr = [10, -15, 2, 25, -16, -53, 22, 2, 1, -3, 60] the most negative sum is -69 from summing -16 and -53.

Another example you have arr = [10, -15, -2, 10, -16, -53, 22, 2, 1, -3, 60] the most negative sum is -76 from summing -15, -2, 10, -16, -53.

Upvotes: 0

Views: 1079

Answers (1)

pkd
pkd

Reputation: 523

You can use the standard Kadane’s algorithm, just change the sign of array element.

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

Upvotes: 3

Related Questions