Solution for RubyQuiz 131

ruby-talk
1

From: "Jens Häßler" <vikingjens@gmx.de>
Date: August 22, 2007 9:30:51 AM CDT
To: submission@rubyquiz.com <submission@rubyquiz.com>
Subject: Solution for RubyQuiz 131

I really liked thinking about these arrays even if I am a little late...

After a few tries, which compared all possible subarrays, I found a O(n) solution. I like my solution, because it is written in a quite simple style.
The algorithm does add the numbers until the sum is getting smaler then 0. If thats the case, then it would make no sence to add this subarray with following subarrays, because they would become smaller.

Thats the idea and because that it is so simple, it quite fast.

def max_subarray(array)
total=array[0]
borders=0..0

first=0
subtotal=0
for last in 0..(array.length-1) do
  subtotal+=array[last]
  if subtotal>total then
   total=subtotal
   borders=first..last
  end

  if subtotal<=0 then
   first=last+1
   subtotal=0
  end
end

return [total, borders]
end

I also had some ideas about the matrices. First, of course, I compared all possible submatrices. Fast programmed but extreme slow, especially with larger matrices.

So the idea is, to create an algorithm, that uses the max_subarray method within. I'm generating the rows by adding rows together and I'm doing this with all possible combination of the rows.
(with 3 rows: 0, 0+1, 0+1+2, 1, 1+2, 2)

def max_submatrix(matrix)
total=matrix[0][0]
borders_row=0..0
borders_column=0..0

for first in 0..(matrix.length-1) do
  array=Array.new(matrix[first].length){0}
  for last in (first)..(matrix.length-1) do
   for index in 0..(matrix[last].length-1) do
    array[index]+=matrix[last][index]
   end

   subtotal=max_subarray(array)
   if subtotal[0]>total then
    total=subtotal[0]
    borders_row=subtotal[1]
    borders_column=first..last
   end
  end
end

return [total, borders_row, borders_column]
end

Because I use all combinations of the colums, the algorithm slows extremly down when the matrix consists of one large column like (1, 500). In that case, the max_subarray method is not going into action (its just comparing the rows, consisting of one number) and we are comparing all possible combinations.

So what I decided to do is to tell the algorithm to reverse the matrix. A (1, 500) matrix would become a (500, 1) matrix and the max_subarray method only has to run one time through the matrix. I reverse the matrix when there are more rows than columns. The less rows the faster comparing.
I did not reverse the matrix manually. I did more tell the programm which indices had to be permuted.

def max_submatrix_2(matrix)
if matrix.length<=matrix[0].length then
  row=matrix.length
  column=matrix[0].length
  reverse=false
else
  row=matrix[0].length
  column=matrix.length
  reverse=true
end

total=matrix[0][0]
borders_row=0..0
borders_column=0..0

for first in 0..(row-1) do
  array=Array.new(column){0}
  for last in (first)..(row-1) do
   if reverse then
    for index in 0..(column-1) do
     array[index]+=matrix[index][last]
    end

    subtotal=max_subarray(array)

    if subtotal[0]>total then
     total=subtotal[0]
     borders_row=first..last
     borders_column=subtotal[1]
    end
   else
    for index in 0..(column-1) do
     array[index]+=matrix[last][index]
    end

    subtotal=max_subarray(array)

    if subtotal[0]>total then
     total=subtotal[0]
     borders_row=subtotal[1]
     borders_column=first..last
    end
   end
  end
end

return [total, borders_row, borders_column]
end

Its nice to see, that these ones are so fast.
For a (1000, 80) matrix, max_submatrix_2(matrix) needs 14sec, for (1000000, 1) 4sec and for (1, 1000000) also 4sec.

Was fun programming this.
--
GMX FreeMail: 1 GB Postfach, 5 E-Mail-Adressen, 10 Free SMS.
Alle Infos und kostenlose Anmeldung: GMX E-Mail ✉ sichere & kostenlose E-Mail-Adresse ✉

···

Begin forwarded message: