From: Anton <selecter@...>
Date: 2007-07-16T00:04:19+09:00
Subject: [Solution] [Quiz] Maximum Sub-Array (#131)

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.

Comments concerning the algorithm:
1. I decided that it's OK to truncate all negative elements at the
both sides of an array. They really do not do any good and do not
promise any positive elements behind them.

2. I built a sumtree walking an array and summing each pair into the
next tree that is smaller than a previous one until I got 1 element
left (which is the root). You can understand the idea easily if you
draw it on a piece of paper. And I also built another tree with
different pairs. That's why I added variable - mb(magic byte).

3. sumtree.flatten.max returns a max subtree.

4. Then I found a formula to find where exactly I should cut a sub-array.
length = 2.power!(max[0])
from = length * max[1]
and used it to find a contender subarray. Why contender? Because it is
needed to use another tree which is built in a different way with
different pairs.

5. At the end I find a subarray or subarrays from contenders with a max sum.

Please don't kick me hard if something is incorrect :P And I would
like to get a few suggestions about improvements and corrections of
my, maybe dirty, ruby coding style.

http://pastie.caboo.se/78977

#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 = []
	answers_sums = []
	
	0.upto(1) do |mb| #magic byte
		level = 0
		sumtree = []
		sumtree[0] = 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[0])
			from = length * max[1]
			
			if mb == 1
				from -= 1
				length += 1
			end
			
			contender_subarray = sumtree.first[from, length]
			contenders << contender_subarray
			#puts "Contender sub-array: #{contender_subarray.inspect}".green.bold
			answers_sums << contender_subarray.inject {|a,b| a+b}
		end
	end
	
	winners = []
	max = answers_sums.max()
	answers_sums.each_index do |i|
		winners << i if answers_sums.at(i).eql?(max)
	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[0].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

#1st solution

require 'term/ansicolor'
include Term::ANSIColor

class Array
	def sum_all_elements
		self.inject {|a,b| a + b}	
	end
end

def find_min(arr)
	arr = arr.dup
	arr.collect! {|n| if n < 0 then n end}
	arr.compact!
	arr.empty? ? 0 : arr.sum_all_elements()
end

def max_sub_array(arr)
	max = find_min(arr)
	sub_arrays = []
	(0...arr.size).each() do |n|
		(1..arr.size-n).each() do |n2|
			sum = arr[n, n2].sum_all_elements()
			#puts arr[n, n2].inspect() + " = " + sum.to_s() #DEBUG LINE
			if sum == max
				sub_arrays << arr[n, n2].inspect()
			elsif sum > max
				max = sum
				sub_arrays = []
				sub_arrays << arr[n, n2].inspect()	
			end
		end	
	end
	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[0].to_i
		end
	else
		raise "Please specify an array in [a, b, c] format"	
	end
	
	
	puts "Max sub-arrays are: #{max_sub_array(arr).inspect.green.bold}"
rescue RuntimeError => e
	$stderr.puts e.message()
end