Python Maximum sum of a range in an array
arrays, python, sum
Solution
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
Problem
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 ```