Forum: Ruby Maximum Sub-Array (#131)

Announcement (2017-05-07): is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see and for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-07-19 14:52
(Received via mailing list)
This is a classic algorithmic challenge and despite its seeming
there's quite a bit you can learn from it.  I'm pretty sure it was this
problem that finally got Big O Notation through my thick skull, so I'll
that approach with this summary.

The obvious code that tends to come to mind for solving this problem is
brute-force search through the subarrays.  That's not a bad thing.  It's
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 Olson:

  class Array
    # sum the integer values of array contents
    def int_sum
      self.inject(0){|sum,i| sum+i.to_i}

    # 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]

  # 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}"

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,
all possible lengths, to check each subarray.  Each subarray is tested
the current best sum and the end result is that the highest total found
will be

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

  $ time ruby -r max_sub_array -e 'p [-1, 2, 5, -1, 3, -2,
  [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 { 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 { 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.
fact, that inner each() is called 500,500 times for an Array with 1,000
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
across this solution from Justin Either:

  $ time ruby -r max_sub_array
              -e 'p { 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 { 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 { 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

   # Set boundaries of the sub-array
   def set_bounds(list_start, list_end)
     @start, @end = list_start, list_end

   # Provide get/set accessors
   attr_reader :start, :end, :sum
   attr_writer :sum

  class MaxSubArray
   # Finds the sub-array with the largest sum
   # Input: a list of integers
   def find(list)
     max =
     cur =

     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)

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

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

The second class holds the actual algorithm.  The trick here is pretty
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
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,
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 Quiz will now take a one week break to allow everyone the chance to
in the ICFP Contest (  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!
This topic is locked and can not be replied to.