max_subarray.rb

# http://stackoverflow.com/a/7944434/996825

def max_subarray(a)
    sum = [0]
    max, head, tail = sum[0], -1, -1
    cur_head = 0

    (0...a.size).each do |j|
        # base case included below since sum[-1] = sum[0]
        sum[j] = [0, sum[j-1] + a[j]].max
        cur_head = j if sum[j-1] == 0
        if sum[j] > max
            max, head, tail = sum[j], cur_head, j
        end
    end

    return max, head, tail
end

# -----------------------------------------------------------------------------
# TESTS

tests = [ # [ input, expected ]
    [ [],           [0, -1, -1] ],
    [ [0],          [0, -1, -1] ],
    [ [3],          [3, 0, 0] ],
    [ [-3, -6, -1], [0, -1, -1] ],
    [ [4, -2, -8, 5, -2, 7, 7, 2, -6, 5 ], [19, 3, 7] ],
    [ [-100, 100, -1, 100, -100], [199, 1, 3] ]
]

$input_width = 40
$expected_width = 18

def verify(method, input, expected)
    output = method.call(input)
    printf "%-#{$input_width}s%-#{$expected_width}s", "#{input}", "#{expected}"
    if expected == output
        puts "pass"
        return 0
    else
        puts "fail, got #{output}"
        return -1
    end
end

printf "%-#{$input_width}s%-#{$expected_width}s%s\n", \
        "input", "expected", "result"
printf "%-#{$input_width}s%-#{$expected_width}s%s\n", \
        "-----", "--------", "------"
puts

for test in tests
    verify method(:max_subarray), test[0], test[1]
end

output.txt

$ ruby max_subarray.rb 
input                                   expected          result
-----                                   --------          ------

[]                                      [0, -1, -1]       pass
[0]                                     [0, -1, -1]       pass
[3]                                     [3, 0, 0]         pass
[-3, -6, -1]                            [0, -1, -1]       pass
[4, -2, -8, 5, -2, 7, 7, 2, -6, 5]      [19, 3, 7]        pass
[-100, 100, -1, 100, -100]              [199, 1, 3]       pass