# Fwd: Maximum Sub-Array (#131)

**URL:** <https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527>\
**Category:** Ruby\
**Created:** [July 16, 2007, 5:34pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527 "2007-07-16T17:34:34Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![okkezSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/o/85f322/32.png) [@okkezSS](https://www.ruby-forum.com/u/okkezSS)\
**Post date:** [July 16, 2007, 5:34pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527/1 "2007-07-16T17:34:34Z")

</div>

Begin forwarded message:

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [July 16, 2007, 5:41pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527/2 "2007-07-16T17:41:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [July 16, 2007, 6:02pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527/3 "2007-07-16T18:02:38Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [July 16, 2007, 7:26pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527/4 "2007-07-16T19:26:46Z")

</div>

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

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 🙂

All in all, matter of specifications.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [July 16, 2007, 6:40pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527/5 "2007-07-16T18:40:42Z")

</div>

On 7/16/07, Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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).

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 25, 2007, 11:04pm UTC](https://www.ruby-forum.com/t/fwd-maximum-sub-array-131/198527/6 "2007-09-25T23:04:11Z")

</div>

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

> > [rubyquiz.com](http://rubyquiz.com) instead?  
> > Sorry, I didn’t notice this message was sent to Ruby T. before it  
> > was sent to me. I didn’t mean to duplicate it.

James Edward G. II