Python Maximum sum of a range in an array

Question

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

Your question is a good reason to teach yourself a little bit about dynamic programming stackoverflow.com/q/1065433/2282538 — Tyler
– Tyler, Commented Nov 21, 2013 at 17:31

Calvin Froedge · Accepted Answer · 2014-08-13 02:34:34Z

4

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

edited Aug 13, 2014 at 2:34

Calvin Froedge

16.4k17 gold badges58 silver badges62 bronze badges

answered Nov 21, 2013 at 17:22

ffledgling

12.3k8 gold badges52 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

PenguinProgrammer Over a year ago

I've been playing with this for a bit but, how can I use it it determine the starting and ending index of the subarray

dansalmo · Accepted Answer · 2013-11-21 17:45:19Z

1

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:]

edited Nov 21, 2013 at 17:45

answered Nov 21, 2013 at 17:26

dansalmo

11.7k5 gold badges62 silver badges55 bronze badges

Collectives™ on Stack Overflow

Python Maximum sum of a range in an array

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related