Maximum Subarray

max_subarray.rb

#!/usr/bin/env ruby

# Maximum Subarray

# Using any language or technique, write a program that meets the following criteria:

# Given an array containing positive and negative integers, return the maximum sum that
# can be generated from any contiguous set.

# For example in the following array:
# [-4,  5,  5, -7,  4, -1,  8, -6]
# The maximum subarray value is 14 coming from the continuous set [5,  5, -7,  4, -1,  8].

# For testing use the following arrays which are preceeded by their expected result:
# 14 = [-4,  5,  5, -7,  4, -1,  8, -6]
# 12 = [ 2, -3,  6,  5, -1,  2, -4,  3]
# 8 = [ 2,  5, -8, -3,  8, -2, -9,  7]
# 12 = [-4, -3,  6,  6, -9,  4, -9,  8]


def max_subarray( arr )
  max = 0

  # choose a starting point in the array
  (0..arr.length-1).each do |start|
    result = 0

    # loop forward through array elements
    (start..arr.length-1).each do |num|
      result += arr[num]
      max = result if result > max
    end
  end

  puts max
end

max_subarray [-4,  5,  5, -7,  4, -1,  8, -6]  # 14
max_subarray [ 2, -3,  6,  5, -1,  2, -4,  3]  # 12
max_subarray [ 2,  5, -8, -3,  8, -2, -9,  7]  # 8
max_subarray [-4, -3,  6,  6, -9,  4, -9,  8]  # 12