Fwd: Solution for RubyQuiz 131
- From: James Edward Gray II <james@xxxxxxxxxxxxxxxxxxx>
- Date: Wed, 22 Aug 2007 23:31:55 +0900
Begin forwarded message:
From: "Jens Häßler" <vikingjens@xxxxxx>
Date: August 22, 2007 9:30:51 AM CDT
To: submission@xxxxxxxxxxxx <submission@xxxxxxxxxxxx>
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
.
- Prev by Date: Re: How to "cast" in Ruby
- Next by Date: Re: shoes?
- Previous by thread: Re: Call an application from Ruby
- Next by thread: Re: Using external text file to do search and replace?
- Index(es):
Relevant Pages
|
