# Solution for RubyQuiz 131 **URL:** \ **Category:** ruby-talk\ **Created:** [22 August 2007 14:31 UTC](https://rubytalk.org/t/solution-for-rubyquiz-131/40116 "2007-08-22T14:31:55Z")\ **Posts on this page:** 1\ **Page:** 1
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [22 August 2007 14:31 UTC](https://rubytalk.org/t/solution-for-rubyquiz-131/40116/1 "2007-08-22T14:31:55Z")
> From: "Jens Häßler" \ > Date: August 22, 2007 9:30:51 AM CDT > To: 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 ✉](http://www.gmx.net/de/go/freemail) > **···** > > Begin forwarded message: