# Maximum Sub-Array (#131)

**URL:** <https://www.ruby-forum.com/t/maximum-sub-array-131/109836>\
**Category:** Ruby\
**Created:** [July 19, 2007, 2:52pm UTC](https://www.ruby-forum.com/t/maximum-sub-array-131/109836 "2007-07-19T14:52:27Z")\
**Posts on this page:** 1\
**Page:** 1

<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 19, 2007, 2:52pm UTC](https://www.ruby-forum.com/t/maximum-sub-array-131/109836/1 "2007-07-19T14:52:27Z")

</div>

This is a classic algorithmic challenge and despite its seeming  
simplicity,  
there’s quite a bit you can learn from it. I’m pretty sure it was this  
exact  
problem that finally got Big O Notation through my thick skull, so I’ll  
take  
that approach with this summary.

The obvious code that tends to come to mind for solving this problem is  
a  
brute-force search through the subarrays. That’s not a bad thing. It’s  
very  
easy to code up and may work for you if the inputs are small enough. It  
certainly works for the quiz example.

Here’s a solution of that by Drew O.:

class Array  
# sum the integer values of array contents  
def int\_sum  
self.inject(0){|sum,i| sum+i.to\_i}  
end

```
# find the maximum sub array in an array
def max_sub_array
  (0...self.size).inject([self.first]) do |max_sub,i|
    (i...self.size).each do |j|
      if max_sub.int_sum < self[i..j].int_sum
        max_sub = self[i..j]
      end
    end
    max_sub
  end
end

```

end

# test example

if **FILE** == $0  
my\_arr = [-1, 2, 5, -1, 3, -2, 1]  
puts “array: #{my\_arr.inspect}”  
puts “maximum sub-array: #{my\_arr.max\_sub\_array.inspect}”  
end

I removed a little of Drew’s printing code in the above so we could  
focus on the  
algorithm, but the results are unchanged.

We can see that Drew’s code works by walking through all of the indices,  
with  
all possible lengths, to check each subarray. Each subarray is tested  
against  
the current best sum and the end result is that the highest total found  
will be  
returned.

The question we want to ask though, is how long does this take for  
various  
inputs? It’s quite zippy for the quiz example:

$ time ruby -r max\_sub\_array -e ‘p [-1, 2, 5, -1, 3, -2,  
1].max\_sub\_array’  
[2, 5, -1, 3]

real 0m0.013s  
user 0m0.007s  
sys 0m0.005s

It slows down pretty quick though, with bigger inputs:

$ time ruby -r max\_sub\_array  
-e ‘p Array.new(100) { rand(11) - 5 }.max\_sub\_array’  
[4, 0, 1, 4, -1, 1, 4, 0, 4, 3, 1, 0, 3, -4, 1, 4, -1, 0, 4, -3, 1,  
-3, 4, 2]

real 0m0.307s  
user 0m0.301s  
sys 0m0.006s  
$ time ruby -r max\_sub\_array  
-e ‘p Array.new(1\_000) { rand(11) - 5 }.max\_sub\_array’  
[3, 1, -3, -1, 2, 5, 4, 3, -5, -2, 3, 1, 1, -2, -3, 4, 5, 4, 4, -3,  
-1, …]

real 3m39.856s  
user 3m38.455s  
sys 0m0.343s

The issue here is that those nested loops just execute many, many times.  
In  
fact, that inner each() is called 500,500 times for an Array with 1,000  
entries.  
If we want to tackle those bigger lists we need to lower that count.

One way to find the algorithms with lower iteration counts is to  
randomly spot  
check the solutions on an Array of similar length. In doing so, I  
stumbled  
across this solution from Justin Either:

$ time ruby -r max\_sub\_array  
-e ‘p MaxSubArray.new.find(Array.new(1\_000) { rand(11) - 5  
})’  
[1, 4, 1, 2, -5, -3, 4, 2, 3, 1, -2, 4, 5, 1, 3, 0, 5, -1, 4, 4, 2, 4,  
…]

real 0m0.016s  
user 0m0.009s  
sys 0m0.006s  
$ time ruby -r max\_sub\_array  
-e ‘p MaxSubArray.new.find(Array.new(10\_000) { rand(11) -  
5 })’  
[3, 1, -2, 5, 4, 5, 0, -3, 0, 3, 5, -3, -4, -3, 5, -3, -1, 4, 5, -3,  
3, …]

real 0m0.047s  
user 0m0.030s  
sys 0m0.006s  
$ time ruby -r max\_sub\_array  
-e ‘p MaxSubArray.new.find(Array.new(100\_000) { rand(11) -  
5 })’  
[4, 1, -2, 3, 4, -4, -4, 4, 5, 1, -3, 4, -5, 5, -5, 1, -1, 0, -5, 1,  
-1, …]

real 0m0.286s  
user 0m0.267s  
sys 0m0.011s

As you can see, that’s scaling to much higher counts much quicker.  
That’s a  
sure sign of a more clever algorithm, so let’s take a peek at the code:

# Object defining a sub-array of integer values

# The sub-array contains a start and end index

# defining a region of the master array

class SubArray  
def initialize  
@start = 0  
@end = 0  
@sum = 0  
end

# Set boundaries of the sub-array

def set\_bounds(list\_start, list\_end)  
@start, @end = list\_start, list\_end  
end

# Provide get/set accessors

attr\_reader :start, :end, :sum  
attr\_writer :sum  
end

class MaxSubArray

# Finds the sub-array with the largest sum

# Input: a list of integers

def find(list)  
max = SubArray.new  
cur = SubArray.new

```
 for i in 0...list.size
   cur.sum = cur.sum + list[i]

   if (cur.sum > max.sum)
     max.sum = cur.sum
     cur.set_bounds(cur.start, i)
     max.set_bounds(cur.start, i)
   elsif (cur.sum < 0)
     # If sum goes negative, this region cannot have the max sum
     cur.sum = 0
     cur.set_bounds(i + 1, i + 1)
   end
 end

 list.slice(max.start, max.end - max.start + 1)

```

end  
end

First, you need to take a look at the SubArray class. This is just a  
bookkeeping tool to keep track of the bounds and sum of any given  
subarray.  
There is a minor bug here that hinders this solution on all-negative  
Arrays like  
[-3, -1], but it can be fixed by initializing sum to -1.0/0.0 instead of  
0.

The second class holds the actual algorithm. The trick here is pretty  
simple  
once you’ve seen it before. Basically, we start from the beginning of  
the Array  
and expand the subarray to following indices. We keep track of the best  
total  
seen thus far and replace that when we find better totals.

The trick is that we hop our subarray indices forward whenever the  
running total  
dips into the negatives. A negative total is effectively starting over,  
so  
skipping over all of those numbers costs us nothing. The run is broken.

This algorithm in linear, so that for iterator only executes 1,000 times  
for an  
Array of that length. That’s where your big speed gain comes from in  
this case  
and the reason algorithms are important when dealing with larger inputs.

My thanks to all the algorists that showed off the variety of solutions  
that can  
be applied here.

Ruby Q. will now take a one week break to allow everyone the chance to  
compete  
in the ICFP Contest ([http://www.icfpcontest.org/](http://www.icfpcontest.org/)). If you are a fan of  
programming contests, I strongly encourage you to give this yearly  
competition a  
shot. It’s always challenging and rewarding. Best of luck!