CODEWITHSUNDEEP
pythonarrayssum
PenguinProgrammer
PenguinProgrammer

Reputation: 141

Python Maximum sum of a range in an array

Trying to create a function where an array a is passed as an argument and what is returned is a pair of indices x,y such that the maximum sum is sum(a[x:y]).

For example, let's say I have the array [4, -2, -3, 7, 3, -1]. The function would take in this array and spit out (3, 4) because the sequence of number from index 3 to index 4 is the biggest one you can make in this array. 10 is the largest number you'll find in this array from adding any sequence together.

This is the code I have so far, which more or less works, but it takes forever for arrays > 10000 in length. Any suggestions?

def bentley(a):
    max = 0
    indices = 0,0
    for x in range(len(a)):
        for y in range(len(a)):
            if sum(a[x:y]) > max:
                max = sum(a[x:y])
                indices = x,y
    return indices

Upvotes: 3

Views: 4224

Answers (2)

ffledgling
ffledgling

Reputation: 12140

http://en.wikipedia.org/wiki/Maximum_subarray_problem

From wikipedia:

Kadane's algorithm, O(n)

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)

    if max_so_far > 0:
        return max_so_far
    else:
        return max(A)

Alternate Divide and conquer O(nlogn):

http://penguin.ewu.edu/~bojianxu/courses/cscd320/slides_dc_2.pdf

Upvotes: 4

dansalmo
dansalmo

Reputation: 11686

Here it is in a yummy idiom salad: 

def bentley(a):
    return max((sum(a[x:y+1]), x, y) 
                for x, _ in enumerate(a) for y, _ in enumerate(a))[1:]

Upvotes: 1

Related Questions