```On 15/07/07, Anton <selecter / gmail.com> wrote:
> Hornestly, it was the hardest quiz I have ever solved. Maybe because I
> am not so experienced as you are. I have two solutions.
>
> First one is straightforward. It walks an array and finds the max
> sub-array. I wrote it just to get the right answers.
>
> The second one took me almost 15 hours to find and code :( But... it
> seems to work actually! I stopped reading at "Unit testing" so for now
> I don't know how to do that.
> ...

I fixed a small bug in a 2nd solution. Now, all nearby positive
numbers are also added to the sub-array. But, anyway, I found out (on
a 1000-item array) that my code is still not accurate enough. I think
I had to split a large array into small ones first.

http://pastie.caboo.se/78986
#2nd solution

require 'term/ansicolor'
include Term::ANSIColor

def cut_negatives_elements_at_both_sides(arr)
# cut unnecessary negative elements at the start
if arr.first <= 0
arr.each_index() do |i|
if arr.at(i) <= 0
arr.delete_at(i)
retry
else
break
end
end
end

# cut unnecessary negative elements at the end
if arr.last <= 0
(arr.size-1).downto(0) do |i|
if arr.at(i) <= 0
arr.delete_at(i)
retry
else
break
end
end
end
end

def max_sub_array(arr)
cut_negatives_elements_at_both_sides(arr)
contenders = []

0.upto(1) do |mb| #magic byte
level = 0
sumtree = []
sumtree = arr # create level #0

while sumtree[level].size > 1
next_level = level + 1
sumtree[next_level] = []

(0...sumtree[level].size/2).each do |i|
if mb == 1 && level == 0 && i == 0
sumtree[next_level] << sumtree[level].at(0)
next
elsif mb == 1 && level == 0
sumtree[next_level] << sumtree[level].at(i*2-1) +
sumtree[level].at(i*2+1-1)
else
sumtree[next_level] << sumtree[level].at(i*2) + sumtree[level].at(i*2+1)
end
end

if mb == 1 && level == 0 && sumtree[level].size % 2 == 0
sumtree[next_level] << sumtree[level].last
end

if sumtree[level].size % 2 != 0
sumtree[next_level] << sumtree[level].last
end

level += 1
end

#puts "sumtree: #{sumtree.inspect}" #DEBUG CHECK
#puts "Max: #{sumtree.flatten.max()}".red.bold

max_sum = sumtree.flatten.max()
max_at = [] #array of max_sum coordinates [[x,y], [x,y] ...]
sumtree.each_index() do |i|
sumtree.at(i).each_index() do |j|
if sumtree.at(i).at(j) == max_sum
max_at << [i,j]
end
end
end
max_at.each do |max|
#puts "Coords: #{max.inspect}".blue.bold
length = 2.power!(max)
from = length * max

if mb == 1
from -= 1
length += 1
end

contender_subarray = sumtree.first[from, length]
left_part = []
unless from.zero?
(from-1).downto(0) do |i|
if sumtree.first.at(i) >= 0
left_part << sumtree.first.at(i)
else
break
end
end
end
right_part = []
(from+length).upto(sumtree.first.size-1) do |i|
if sumtree.first.at(i) >= 0
right_part << sumtree.first.at(i)
else
break
end
end

contender_subarray = left_part.reverse + contender_subarray + right_part
puts contender_subarray.inspect
contender_subarray.flatten!

unless contenders.include?(contender_subarray)
contenders << contender_subarray
#puts "Contender sub-array: #{contender_subarray.inspect}".green.bold
end
end
end

winners = []
end

winners_sub_arrays = []
winners.each do |i|
winners_sub_arrays << contenders.at(i)
end

return winners_sub_arrays
end

begin
arr = Array.new
arr_str = ARGV.to_s
if arr_str =~ /\A\s*\[\s*-?\d+(?:\s*,\s*-?\d+)*\s*\]\s*\Z/
for el in ARGV do
el = el.match(/(\-*\d+)/)
arr << el.to_i
end
else
raise "Please specify an array in [a, b, c] format"
end
sub_arr = max_sub_array(arr)

if sub_arr.size > 1
puts "Max sub-arrays are: #{sub_arr.inspect()}".blue.bold
else
puts "Max sub-array is: #{sub_arr.inspect()}".blue.bold
end
rescue RuntimeError => e
\$stderr.puts e.message()
end

```