Maximum contiguous sum in an array 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] &gt; 0:
        array[i] = array[i] + array[i-1]
    else: 
        array[i-1] = 0
print(max(array))
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] &gt; 0:
            array[i] = array[i] + array[i-1]
            if array[i] &gt; 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.