Begin forwarded message:

> 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: http://www.gmx.net/de/go/freemail