[Quiz] Maximum Sub-Array (#131)

Ruby
1

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 :frowning: 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 :stuck_out_tongue: 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(i2+1-1)
else
sumtree[next_level] << sumtree[level].at(i2) +
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

2

On 15/07/07, Anton [email protected] 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 :frowning: 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 = []
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(i2+1-1)
else
sumtree[next_level] << sumtree[level].at(i2) +
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]
  # add nearby positive numbers
  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
    answers_sums << contender_subarray.inject {|a,b| a+b}
    #puts "Contender sub-array:

#{contender_subarray.inspect}".green.bold
end
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

3

On 15/07/07, Anton [email protected] wrote:

…

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.

Fixed another bug…

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(i2+1-1)
else
sumtree[next_level] << sumtree[level].at(i2) +
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]
  # add nearby positive numbers
  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
cut_negatives_elements_at_both_sides(contender_subarray)
contender_subarray.flatten!

  unless contenders.include?(contender_subarray)
    contenders << contender_subarray
    answers_sums << contender_subarray.inject {|a,b| a+b}
    #puts "Contender sub-array:

#{contender_subarray.inspect}".green.bold
end
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