[QUIZ] Maximum Sub-Array (#131)

[Matthew Rudy]

this is my first entry
(only found this place last week)

so it's late,
but I like it.

I deal with left-subarrays, and right-subarrays
(i decided that intuitively a max sub array is a max left of a max
right,
but have not the time to prove this)
I also assume that the empty array [] is always a member.

also, my max_left_of_right and max_right_of_left methods will return
multiple copies of the empty array if that is indeed the smallest.

I did initially uniq the result,
but decided against it in the end
(who says that the empty array is a unique sub array -- probably me)

class Array

# solution 1
def max_subs
max_found, max_instances = 0, [[]] # the empty sub array will
always return 0 sum
self.left_subs.each do |l_sub|
next if l_sub.last.nil? || l_sub.last < 0 # if
l_sub.right_subs.each do |sub|
next if sub.first.nil? || sub.first < 0
if (sub_sum = sub.sum) > max_found
max_found, max_instances = sub_sum, [sub]
elsif sub_sum == max_found
max_instances << sub
end
end
end
return max_instances
end

# i hypothesise that each max sub array is actually;
# a max left sub of a max right sub, and the other way round
# but i dont have time to prove it

# solutions 2 and 3
def max_left_of_right
max_right_subs.inject([]){|rtn, max_r| rtn + max_r.max_left_subs}
end

def max_right_of_left
max_left_subs.inject([]){|rtn, max_l| rtn + max_l.max_right_subs}
end


# sub methods

def left_subs
if (l_sub = self.dup) && l_sub.pop
return (l_sub.left_subs << self.dup)
else
return [self]
end
end

def right_subs
if (r_sub = self.dup) && r_sub.shift
return (r_sub.right_subs << self.dup)
else
return [self]
end
end

def sum
self.inject(0){|sum, element| sum+element}
end

def max_left_subs
max_of_subsleft_subs)
end

def max_right_subs
max_of_subsright_subs)
end

def max_of_subs(method)
max_found, max_instances = 0, [[]] # we expect to have an empty sub
self.send(method).each do |sub|
if (sub_sum = sub.sum) > max_found
max_found, max_instances = sub_sum, [sub]
elsif sub_sum == max_found
max_instances << sub
end
end
return max_instances
end
end

 

[Matthew Moss]

Eh.... I got some better quizzes in mind than debugging my lousy
code... I just have to write them up. (This thing called "day job"
keeps getting in the way...)

 

[James Edward Gray II]

Eh.... I got some better quizzes in mind than debugging my lousy
code... I just have to write them up. (This thing called "day job"
keeps getting in the way...)

I always enjoy your quizzes Matthew. Looking forward to it.

James Edward Gray II

 

[Yossef Mendelssohn]

Oh, these quizzes. I need to either find more time to play with them
or stop telling myself I don't have the time. I did this in Perl for
a job interview a while ago and happened to still have it handy, so
all I did was translate it (somewhat) into Ruby.

-------------------------------------------------------------------------------
class Array
def largest_sum_sequence
# initialize with a sequence of the first number
largest = {
:sum => first,
:start => 0,
:end => 0
}

(0 .. length-1).each do |start_i|
sum = 0
start_num = self[start_i]

# don't bother with a sequence that starts with a negative number
# but what if all the numbers are negative?
next if largest[:sum] > start_num and start_num < 0

(start_i .. length-1).each do |end_i|
end_num = self[end_i]
sum += end_num

# if this sequence is the largest so far
if sum > largest[:sum]
largest[:sum] = sum
largest[:start] = start_i
largest[:end] = end_i
end
end
end

puts "Largest sum: #{largest[:sum]}"
puts "The sequence starts at element #{largest[:start]} and goes to
element #{largest[:end]}"
puts "The sequence is #{self[largest[:start] ..
largest[:end]].join(' ')}"
end
end

numbers = ARGV.collect { |arg| arg.to_i }

numbers.largest_sum_sequence