From: Eric Mahurin <eric.mahurin@...>
Date: 2007-07-16T04:18:09+09:00
Subject: Re: [QUIZ-Solution] Maximum Sub-Array (#131)

Here is a O(n) solution.  This simply finds the max accumulation minus
the min accumulation.  I haven't done too much testing, so I don't
know if it handles all of the corner cases.

def max_subarray(seq)
    max_sum = 0
    min_sum = 0
    max_i = -1
    min_i = -1
    sum = 0
    seq.each_with_index { |val,i|
        sum += val
        if sum>max_sum
            max_sum = sum
            max_i = i
        end
        if sum<min_sum
            min_sum = sum
            min_i = i
        end
    }
    if min_i>max_i
        min_sum = 0
        min_i = -1
    end
    seq[(min_i+1)...(max_i+1)]
end