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 http://stackoverflow.com/q/1065433/2282538 — Tyler, Nov 21 '13 at 17:31

score 4 · Accepted Answer · edited Aug 13 '14 at 02:34

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 '14 at 02:34

Calvin Froedge

16,135
16
55
61

answered Nov 21 '13 at 17:22

ffledgling

11,502
8
47
69

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 – PenguinProgrammer Nov 21 '13 at 20:41

dansalmo · Answer 2 · 2013-11-21T17:45:19.687

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 '13 at 17:45

answered Nov 21 '13 at 17:26

dansalmo

11,506
5
58
53

Python Maximum sum of a range in an array

2 Answers2