Asp Forum - Fwd: Solution for RubyQuiz 131

James Gray

8/22/2007 2:32:00 PM

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/g...

comp.lang.ruby

Fwd: Solution for RubyQuiz 131

James Gray

x Login to ForumsZone