Maximum contiguous sum in an array

Question

The following code is my solution for the following Daily Coding Challenge

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take elements 42, 14, -5, and 86.

Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would not take any elements.

Do this in O(N) time.

I think this is done in O(N) time and is the best solution. If someone can think of a better way, I would be interested.

array = [4, -2, 7, -9]
running_sum = 0
for i in range(1,len(array)):
 if array[i-1] > 0:
 array[i] = array[i] + array[i-1]
 else: 
 array[i-1] = 0
print(max(array))

• dfhwze: You can remove running_sum = 0 :)
• vnp: Although it is not specified in the problem statement, the space complexity is also important. Your algorithm exhibits an \$O(n)\$ time complexity (because it mutates an array). There exists a constant space, linear time solution.
• MrJoe: Surely you have to store the array to process it. Therefore my not making a new variable, the space complexity is the same? @vnp
• vnp: The space complexity does not account for the space taken by the input.
• MrJoe: I am curious how this would work. Because saying something like max_value = maximum(max_value, max_value + array[i]) wouldn't work. How can you predict the i+1 or i+2 value in linear time complexity. Any clues? Thanks

Answer 1

changing mutable object

Since you are changing the original array, this code run twice can provide strange results. In general I try to avoid changing the arguments passed into a function I write, unless it's explicitly stated, or expected (like list.sort)

accumulate

What you are looking for is the largest difference between tha cumulative sum where the minimum comes before the maximum. Calculating the cumulative sum can be done with itertools.accumulate. Then you just have to keep track of the minimum of this running sum and the difference with the running minimum

def best_sum_accum(array):
 running_min = 0
 max_difference = 0
 for cumsum in accumulate(array):
 if cumsum > running_min:
 max_difference = max(max_difference, cumsum - running_min)
 running_min = min(running_min, cumsum)
 return max_difference

• MrJoe: Surely this has a time complexity > O(N) because you have a nested loop? for and max?
• Maarten Fabré: Not really, you loop 1 timer through the array. On each iteration, you compare 2 numbers, so the time complexity is linear with the length of the array. Space complexity is constant

Answer 2

I would merge the 2 loops (there is one in the max part), since not all parts are relevant for the maximum:

def best_subsum(array):
 running_sum = 0
 for i in range(1,len(array)):
 if array[i-1] > 0:
 array[i] = array[i] + array[i-1]
 if array[i] > running_sum: running_sum = array[i]
 return running_sum
array = [4, -2, 7, -9]
print(best_subsum(array))

Note that branch prediction shouldnt be too much of a problem, since running sum is not check until the same if statement in the next succeding iteration.