From: Eric Mahurin <eric.mahurin@...>
Date: 2007-07-17T01:39:54+09:00
Subject: Re: [QUIZ-Solution] Maximum Sub-Array (#131)

On 7/16/07, Matthew Moss <matthew.moss.coder@gmail.com> wrote:
> > > irb(main):007:0> max_subarray([-10] )
> > > => []
>
> I would say this is wrong. Despite being a negative sum, the non-empty
> subarray [-10] still has the maximum sum.

It depends on how you want to define the sum of an empty array - zero
or undefined/invalid.  I prefer to define sum of an enumerable like
this:

inject(0) {|sum,v| sum+=v}

Or, if you wanted to apply more duck typing, you could define a
generic Zero object that plays well with anything comparable and that
has a unary minus:

inject(Zero) {|sum,v| sum+=v}

where Zero is something like:

Zero = Object.new
class << Zero
    include Comparable
    def to_s
        "Zero"
    end
    def +(other)
        other
    end
    def -(other)
        -other
    end
    def <=>(other)
        -other<=>other
    end
end


You could extend this idea to a variety of singleton objects that
mimic basic numbers and can be defined by the other "number" involved
in each operation:

+infinity (i.e. +infinity*anthing==+infinity, (+inifinity<=>anything)==1
-infinity
+1 (i.e. 1*thing==thing, 1+thing==thing.succ)
-1 (i.e. (-1)*thing==-thing)
+0 (i.e. anything/+0 == +infinity)
-0

I find +infinity and -infinity singleton objects particularly helpful
especially since there isn't a portable way to represent these with
built-in objects.  I call these singleton objects Max and Min.  Many
times these help refactor/DRY my code because I don't have to treat my
first iteration differently since I can initialize appropriate
variables to Max/Min (+inf/-inf).