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))