[QUIZ-Solution] Maximum Sub-Array (#131)

ruby-talk
1

From: "Eric Mahurin" <eric.mahurin@gmail.com>
Date: July 16, 2007 8:13:56 AM CDT
To: "James Edward Gray II" <james@grayproductions.net>
Subject: Fwd: [QUIZ-Solution] Maximum Sub-Array (#131)

James,

I messed up on my first solution. Could you put this on rubyquiz.com instead?

Thanks,

Eric

From: Eric Mahurin <eric.mahurin@gmail.com>
Date: Jul 15, 2007 9:20 PM
Subject: Re: [QUIZ-Solution] Maximum Sub-Array (#131)
To: ruby-talk ML <ruby-talk@ruby-lang.org>

> Here is a O(n) solution. This simply finds the max accumulation minus
> the min accumulation. I haven't done too much testing, so I don't
> know if it handles all of the corner cases.
>
> <snip>

FYI, your solution does indeed fail in some cases:

irb(main):052:0> arr = [-2,0,0,4,-5,1]
=> [-2, 0, 0, 4, -5, 1]
irb(main):053:0> max_subarray arr
=> [-2, 0, 0, 4]

Thanks for pointing out my mistake. I didn't handle the case when the
min accumulation comes after the max accumulation very well. Now it
records the min index when it finds the best sub-array sum so far
(instead of blindly subtracting min from max at the end). Here is a
corrected version w/ some testing in irb:

def max_subarray(seq)
   min_sum = 0
   min_i = -1
   max_delta = 0
   max_i = -1
   max_i0 = -1
   sum = 0
   seq.each_with_index { |val,i|
       sum += val
       delta = sum-min_sum
       if delta>max_delta
           max_delta = delta
           max_i = i
           max_i0 = min_i
       end
       if sum<min_sum
           min_sum = sum
           min_i = i
       end
   }
   seq[(max_i0+1)...(max_i+1)]
end

irb(main):001:0> require 'quiz131'
=> true
irb(main):002:0> max_subarray([-1, 2, 5, -1, 3, -2, 1])
=> [2, 5, -1, 3]
irb(main):003:0> max_subarray([-2,0,0,4,-5,1])
=> [0, 0, 4]
irb(main):004:0> max_subarray([-1, 2, 5, -1, 3, -2, 1])
=> [2, 5, -1, 3]
irb(main):005:0> max_subarray([31, -41, 59, 26, -53, 58, 97, -93, -23, 84] )
=> [59, 26, -53, 58, 97]
irb(main):006:0> max_subarray()
=>
irb(main):007:0> max_subarray([-10] )
=>
irb(main):008:0> max_subarray([10])
=> [10]
irb(main):009:0> max_subarray([-5, 5])
=> [5]
irb(main):010:0> max_subarray([5, -5])
=> [5]

···

Begin forwarded message:

---------- Forwarded message ----------
On 7/15/07, Jesse Merriman <jesse.d.merriman@gmail.com> wrote:

On Sunday 15 July 2007 15:18, Eric Mahurin wrote:

2

Sorry, I didn't notice this message was sent to Ruby Talk before it was sent to me. I didn't mean to duplicate it.

James Edward Gray II

···

On Jul 16, 2007, at 9:02 AM, James Edward Gray II wrote:

Begin forwarded message:

From: "Eric Mahurin" <eric.mahurin@gmail.com>
Date: July 16, 2007 8:13:56 AM CDT
To: "James Edward Gray II" <james@grayproductions.net>
Subject: Fwd: [QUIZ-Solution] Maximum Sub-Array (#131)

James,

I messed up on my first solution. Could you put this on rubyquiz.com instead?

3

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

4

That's what I said too, early in the quiz discussion.

However, it should be noted that the empty Array (considered to have a sum of zero) is very common in the various versions of this problem around the net. I've been looking a little.

James Edward Gray II

···

On Jul 16, 2007, at 9:56 AM, Matthew Moss 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.

5

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).

···

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.

6

I think it makes more sense to choose the zero length array from the point
of view of gambling or even better investing money in stocks. The way
you're making the most money in a crisis is to avoid investing alltogether.

Well, you can do "down speculation" (sorry, don't know the expression in
english) and get more stocks for the same money but that's the dual problem :slight_smile:

All in all, matter of specifications.

···

On Mon, 16 Jul 2007 23:56:00 +0900, Matthew Moss 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.

--
goto 10: http://www.goto10.it
blog it: http://riffraff.blogsome.com
blog en: http://www.riffraff.info