# \[Quiz\] Maximum Sub-Array (#131)

**URL:** <https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109481>\
**Category:** Ruby\
**Created:** [July 15, 2007, 5:05pm UTC](https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109481 "2007-07-15T17:05:51Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![anton](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d9b06d/32.png) [@anton](https://www.ruby-forum.com/u/anton)\
**Post date:** [July 15, 2007, 5:05pm UTC](https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109481/1 "2007-07-15T17:05:51Z")

</div>

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 😛 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](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

---

<div class="post-metadata">

**Author:** ![anton](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d9b06d/32.png) [@anton](https://www.ruby-forum.com/u/anton)\
**Post date:** [July 15, 2007, 6:33pm UTC](https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109481/2 "2007-07-15T18:33:59Z")

</div>

On 15/07/07, Anton [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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](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(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]
  # 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

---

<div class="post-metadata">

**Author:** ![anton](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/d9b06d/32.png) [@anton](https://www.ruby-forum.com/u/anton)\
**Post date:** [July 15, 2007, 6:52pm UTC](https://www.ruby-forum.com/t/quiz-maximum-sub-array-131/109481/3 "2007-07-15T18:52:00Z")

</div>

On 15/07/07, Anton [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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(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]
  # 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