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.

daily-coding-problem-49.rb

#!/usr/bin/env ruby

def max_sum(array)
    max_so_far = 0 
    max_ending_here = 0
    array.each do |i|
        max_ending_here += i
        max_so_far = max_ending_here if max_so_far < max_ending_here
        max_ending_here = 0 if max_ending_here < 0 
    end 
    return max_so_far
end 

arr = [34, -50, 42, 14, -5, 86] 
puts max_sum(arr)