From: "Alexandru E. Ungur" <alexandru@...>
Date: 2007-07-16T00:24:05+09:00
Subject: Re: [QUIZ] Maximum Sub-Array (#131)

--pWyiEgJYm5f9v55/
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hi all,

Here's my solution. It has no other merits than showing me
that I really need to get back to studying algorythms more 
in depth :-) as it's quite slow (needs about 2 minutes for
an 1000 elements array).

There are just two optimisations I came up with:
drop sub arrays starting or ending with negative numbers
and breaking out of loop when the sum of the positive numbers
left is smaller than the maximum we already have.

Cheers,
Alex

--pWyiEgJYm5f9v55/
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="quiz131.rb"

class Array
  def sum() inject{|s,v|s+=v} end

  def max_sub_array
    max = { :sum => 0, :arr => [] }
    max_max = select{|x| x>0}.sum
    0.upto(size-2) do |i|
      next if self[i] < 0
      max_max -= self[i]
      break if max[:sum] > max_max
      i.upto(size-1) do |j|
        next if self[j] < 0
        if (tmp_sum = (tmp_arr = self[i..j]).sum) > max[:sum]
          max[:sum] = tmp_sum
          max[:arr] = tmp_arr
        end
      end
    end
    max
  end
end

if $0 == __FILE__
  ARRR = Array.new(100) { rand(200) - 100 }
  p ARRR.max_sub_array
end

--pWyiEgJYm5f9v55/--