[QUIZ] Maximum Sub-Array (#131)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For example:

  array: [-1, 2, 5, -1, 3, -2, 1]
  maximum sub-array: [2, 5, -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

2

by Harlan

Given an array of integers, find the sub-array with maximum sum. For
example:

        array: [-1, 2, 5, -1, 3, -2, 1]
        maximum sub-array: [2, 5, -1, 3]

Just to confirm the problem. Wouldn't the maximum sub array be

[2, 5, 3] ?

Matt

3

Nice quiz. One question.

For an array containing all negative integers, is the maximimum sub-
array an empty array or a single-value array containing the highest
value?

For example:

array: [-1,-2,-3]

maximum sub-array:
                    or [-1] ?

Regards,

Paul.

···

On Jul 13, 10:29 am, Ruby Quiz <ja...@grayproductions.net> wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For example:

        array: [-1, 2, 5, -1, 3, -2, 1]
        maximum sub-array: [2, 5, -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

4

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For example:

        array: [-1, 2, 5, -1, 3, -2, 1]
        maximum sub-array: [2, 5, -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

···

#
# Here is my solution.
# If there are multiple sub arrays that equal max sum, it prints all of them.

require 'enumerator'
arr, s = [1,5,3,-9,9],
(1..arr.length).each{|q| arr.each_cons(q) {|x| s << x}}
big = s.max {|x,y| x.inject(0) {|a,b| a+b} <=> y.inject(0) {|c,d| c+d}}
p s.select {|r| r.inject(0) {|a,b| a+b} == big.inject(0) {|c,d| c+d}}

# Harry

--
A Look into Japanese Ruby List in English

5

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until 48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone on Ruby Talk follow the discussion. Please reply to the
original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

···

On Fri, 13 Jul 2007 23:29:03 +0900, Ruby Quiz wrote:
=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For
example:

  array: [-1, 2, 5, -1, 3, -2, 1] maximum sub-array:

[2, 5,

  -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

#!/usr/bin/env ruby

require 'matrix'

#strangely, none of these methods are in the facets gem.

module Enumerable
   def argmax
      curmax=nil
      curval=nil
      each do |x|
   t=yield x
   if not curmax or (curmax < t)
      curmax=t
      curval=x
   end
      end
      curval
   end

   def sum
      inject{|a,b|a+b}
   end

   def subarrays
      result=
      (0...length).each do |start|
   ((start + 1)..length).each do |finish|
      result << self[start...finish]
   end
      end
      result
   end
end

class Matrix
   include Enumerable
   def submatrices
      result=
      (0...row_size).each do |srow|
      (srow+1..row_size).each do |erow|
      (0...column_size).each do |scolumn|
      (scolumn+1..column_size).each do |ecolumn|
   result << minor(srow...erow,scolumn...ecolumn)
      end end end end
      result
   end
   def each
      (0...row_size).each do |row|
      (0...column_size).each do |column|
   yield self[row,column]
      end end
   end
end

ARRAY=[-1, 2, 5, -1, 3, -2, 1]
p ARRAY.subarrays.argmax{|x| x.sum}

MATRIX=Matrix[[1,-2,3],[5,2,-4],[5,-5,1]]
p MATRIX.submatrices.argmax{|x| x.sum}

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

6

Ruby Quiz wrote:

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For example:

  array: [-1, 2, 5, -1, 3, -2, 1]
  maximum sub-array: [2, 5, -1, 3]

Extra Credit:
Given a matrix of integers, find the rectangle with maximum sum.

*# The algorithm for max_subarray is a slightly adapted version of
# the linear solution presented in
# "Programming pearls: algorithm design techniques"
# by Jon Bentley, published in Communications of the ACM,
# volume 27, Issue 9 (september 1984). According to the article, it
# was designed by Jay Kadane (in less than a minute) in 1977.
# The algorithm for max_submatrix was inspired by some of the ideas in the same
# article and large quantities of coffee.

# Running time: O(n)
def max_subarray(arr)

  if (max = arr.max) <= 0
    # if all the numbers in the array are less than or equal to zero,
    # then the maximum subarray is simply the array
    # consisting of the largest value
    max_idx = arr.index(max)
    return max, max_idx, max_idx
  end
   # starting index of the maximum subarray
  x1 = 0

  # ending index of the maximum subarray
  x2 = 0
   # the maximum value found so far
  running_max = 0
   # the maximum value of the array ending on the current
  # value (in the block below) or zero, if the maximum
  # array becomes negative by including the current value
  max_ending_here = 0

  # the start index of a possible maximum subarray
  start_idx = 0
   arr.each_with_index do |i, idx|
    start_idx = idx if max_ending_here == 0
    max_ending_here = [0, max_ending_here + i].max
    if max_ending_here > running_max
      running_max = max_ending_here
      x1 = start_idx
      x2 = idx
    end
  end
  return running_max, x1, x2
end

# Running time: O(m^2 * n)
def max_submatrix(matrix)

  # We already have a nice linear algorithm for solving
  # the problem in one dimension. What we want to do is
  # basically to reduce the problem to an array, and then
  # solve that problem using max_subarray.
  # The problem can be solved this way for any contiguous
  # number of rows by simply adding them together, thereby
  # "collapsing" them into one row, and then going from there.
  # Now, we want to do this efficiently, so we create
  # a cumulative matrix, by adding the elements of the columns
  # together. That way, we only need to look up one value
  # pr. column to get the sums of the columns in any sub matrix.
  c_matrix = matrix.inject() do |memo, arr|
    prev_arr = memo.last
    memo << (prev_arr == nil ? arr : Array.new(arr.size) { |i| prev_arr[i] + arr[i] })
  end

  # the maximum value found so far
  running_max = 0
   # starting index of the horizontal maximum subarray
  x1 = 0
   # ending index of the horizontal maximum subarray
  x2 = 0

  # starting index of the vertical maximum subarray
  y1 = 0

  # ending index of the vertical maximum subarray
  y2 = 0
   c_matrix.each_with_index do |c_arr, vert_iter_end|
    0.upto(vert_iter_end) do |vert_iter_start|
      arr = c_arr
      if vert_iter_start != vert_iter_end
        arr = Array.new(c_arr.size) { |i| c_arr[i] - c_matrix[vert_iter_start][i] }
      end
      c_max, hz_s, hz_e = max_subarray(arr)
      if c_max > running_max
        running_max = c_max
        x1, x2, y2 = hz_s, hz_e, vert_iter_end
        y1 = vert_iter_start == vert_iter_end ? 0 : vert_iter_start + 1
      end
    end
  end
  return running_max, x1, x2, y1, y2
end

array = [-1, 2, 5, -1, 3, -2, 1]
max, x1, x2 = max_subarray(array)
puts "Maximum subarray for #{array.inspect}: #{array.values_at(x1..x2).inspect}, sum: #{max}"

matrix =
[
  [ 1, 5, -3, 4],
  [-8, 2, 9, 12],
  [ 6, 1, -2, 2],
  [-3, -15, 7, -6]
]

max, x1, x2, y1, y2 = max_submatrix(matrix)
max_matrix = matrix.values_at(y1..y2).collect { |arr| arr.values_at(x1..x2) }
puts "Maximum submatrix for #{matrix.inspect}: #{max_matrix.inspect}, sum: #{max}"

···

*

7

I went for the all-in-one line solution (not including the method
definition boilerplate), with no consideration for the computational
or memory cost. Here are two versons, the first does not require the
'enumerator' library, the second does and is slightly shorter as a
result. Both will favor shorter solutions over longer solutions if
they have the same sum.

In both cases the code generates every possible sub-array and sorts
them by two factors: 1) sum of elements ascending, and 2) size of sub-
array descending. Finally it chooses the solution at the end of this
sorted list.

In the first solution, it generates every sub-array by using all
possible combinations of starting and ending indices.

def max_sub_array(a)
  (0...a.size).inject([]) { |c, s| c + (s...a.size).map { |e|
a.slice(s..e) } }.sort_by { |b| [b.inject { |s, e| s + e }, -
b.size] }.last
end

In the second solution, it generates every sub-array by sequencing
through all possible sub-array lengths (1..size) and then calling
enum_cons. If you're not familiar with enum_cons, it takes a size as
a parameter and returns an Enumerable for every sub-array of that size
(e.g., [1, 2, 3, 4].enum_cons(2) would provide an Enumerable that
would encode the sequence [1, 2], [2, 3], and [3, 4]).

def max_sub_array2(a)
  (1..a.size).inject([]) { |l, s| l + a.enum_cons(s).to_a }.sort_by { |
b> [b.inject { |s, e| s + e }, -b.size] }.last
end

Eric

···

====
Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com

8

Hi all,

Here's my solution. It has no other merits than showing me
that I really need to get back to studying algorythms more
in depth :slight_smile: as it's quite slow (needs about 2 minutes for
an 1000 elements array).

There are just two optimisations I came up with:
drop sub arrays starting or ending with negative numbers
and breaking out of loop when the sum of the positive numbers
left is smaller than the maximum we already have.

Cheers,
Alex

quiz131.rb (565 Bytes)

9

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

···

On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote:
#
# Here is my matrix solution.
# It does the Matrix extra credit.
# If there are multiple rectangles that equal max sum, it prints all of them.
#
# Since the quiz did not specify how to input,
# I just hard coded a sample Matrix at the beginning.
#

require 'matrix'
mat = Matrix[[77,-1,2,3,-4],[-7,8,-22,10,11],[3,15,16,17,-18],[4,22,-23,-24,-25]]
s =
(0...mat.row_size).each do |a|
  (0...mat.column_size).each do |b|
    (1..mat.row_size).each do |x|
      (1..mat.column_size).each do |y|
      s << mat.minor(a,x,b,y)
      end
    end
  end
end

tot = s.uniq.map {|x| x.to_a}
big = tot.max{|x,y| x.flatten.inject(0) {|a,b| a+b} <=>
y.flatten.inject(0) {|c,d| c+d}}
subs = tot.select {|r| r.flatten.inject(0) {|a,b| a+b} ==
big.flatten.inject(0) {|c,d| c+d}}
puts "Original Matrix"
(0...mat.row_size).each do |x|
print mat.row(x).to_a.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"
end
puts
puts "Solutions"
subs.each do |x|
puts
  x.each {|y| print y.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"}
end

# Harry

--
A Look into Japanese Ruby List in English

10

My solution to Quiz 131. It does a straight-forward O(N**2) search. I did add a constraint: the algorithm should return a sub-array of minimal length. This is because I strongly prefer [0] to [0, 0, 0, 0, 0, 0, 0].

My submission also shows my preference for code that is readable/maintainable rather than golfed/obfuscated. (This is not intended as a shot at those who enjoy code golf -- I'm just saying it's not for me.)

<code>
# Return the non-empty sub-array of minimal length that maximizes the sum
# of its elements.
def max_sub_array(arry)
    max_sum = arry.inject { |sum, n| sum += n }
    min_length = arry.size
    result = arry
    (1...arry.size).each do |i|
       (i...arry.size).each do |j|
          sub = arry[i..j]
          sum = sub.inject { |sum, n| sum += n }
          next if sum < max_sum
          next if sum == max_sum && sub.size >= min_length
          max_sum, min_length, result = sum, sub.size, sub
       end
    end
    result
end
</code>

Regards, Morton

11

I didn't try any golfing, but here are 3 attempts.

The first and second are straightforward approaches, their only difference is
that the second prefers shorter arrays. Both are (n**2 + n) / 2.

The third is my clever solution. I think it should have lower complexity (if
still a factor of n**2), despite having much more setup code, but I'm not sure
what it is exactly. Here's a copy of the main descriptive comment I put in the
code:

# Try to be clever. First, remove any leading or trailing non-positive numbers,
# since including them can only lower the sum. Then, split the array up into
# "islands" of same-sign numbers. Zeros will be including in the group to their
# left. Map each island to its sum to get an array of alternating +,-,+,-,...,+
# numbers. This is really the fundamental form of an instance of the problem.
# It could be run though another max-subarray algorithm, but instead I tried
# to take advantage of its structure by only looking at even-number indices.
# Then just find the maximum subarray's indices, and map back to the originali
# array.

An example in case thats not clear enough:

Start with: [-1, 0, 2, 4, -1, 5, 0, 6, -2]
Trim ends: [2, 4, -1, 5, 0, 6]
Sign switches: [0, 2, 3]
Islands: [[2, 4], [-1], [5, 0, 6]]
new_arr: [6, -1, 11]
Try each index pair: [0, 0], [0, 2], [2, 2]
Best is: [0, 2]
Map back: [2 4 -1 5 0 6]

Only 3 index pairs were tested, as opposed to (9**2 + 9)/ 2 = 45 for the others.

max_subarray.rb (3.93 KB)

···

--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/

12

#!/usr/bin/env ruby

require "rubygems"
require "facets"
require "enumerable/each_unique_pair"
require "enumerable/sum"

class Array
  # all contiguous subarrays
  def sub_arrays
    [*0..self.size].to_enum(:each_unique_pair).map { |a,b|
self[a..b-1] }
  end
end

array = [-1, 2, 5, -1, 3, -2, 1]

# I find this easy on the eyes
array.sub_arrays.max { |a,b| a.sum <=> b.sum } # => [2, 5, -1, 3]

# but if you didn't want to recompute the sums you could do this
array.sub_arrays.map { |a| [a.sum,a] }.max.last # => [2, 5, -1, 3]

···

On Jul 13, 7:29 am, Ruby Quiz <ja...@grayproductions.net> wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For example:

        array: [-1, 2, 5, -1, 3, -2, 1]
        maximum sub-array: [2, 5, -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

13

Just like many others, I went for brute force with some readability.
Golf solution at the bottom.

class Array
  def sum
    inject {|sum, elem| sum + elem}
  end
  def sub_arrays
    subs = []
    0.upto(size-1) { |i| i.upto(size-1) { |j| subs << self[i..j] } }
    subs
  end
end

foo = Array.new(42) { rand(42) - 21 } # build array; choice of
numbers here is arbitrary
p foo << "\n" # show the array
# now show maximum sub-array ...
p foo.sub_arrays.inject([foo.max]) { |max, elem| elem.sum > max.sum ?
elem : max }

Golf solution (3 lines, 120 chars not including array initialization).
I'm sure it could be shorter, though :frowning:

a = Array.new(42){rand(42)-21}

v=[]
0.upto(b=a.size-1){|i|i.upto(b){|j|v<<a[i..j]}}
p v.inject([a.max]){|z,m|z.inject{|s,i|s+i}>m.inject{|s,i|s+i}?z:m}

Todd

14

No extra credit on this one, but my solution handles a regular list of
numbers just fine.
First, I created an object to define a range of numbers:

# 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

Then I created a class to find the sub-array with the maximum sum. Basically
it performs a single pass of the array, updating the maximum sub-array each
time the current sum exceeds the current maximum sum:

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

And finally, here are some tests:

$:.unshift File.join(File.dirname(__FILE__), "..")
require 'test/unit'
require 'max_sub_array.rb'

class TestMaxSubArray < Test::Unit::TestCase
  def setup
    @ma = MaxSubArray.new
  end

  def test_max_sub_array
    assert_equal([2, 5, -1, 3], @ma.find([-1, 2, 5, -1, 3, -2, 1]))
    assert_equal([10], @ma.find([-1, 2, 5, -1, 3, -2, -12, 10]))
    assert_equal(@ma.find([-25, 81, -14, 43, -23, 86, -65, 48]), [81, -14,
43, -23, 86])
    assert_equal([9, 11, 23, -5, 15, 18, 6, -18, 21, -4,
                           -17, -19, -10, -9, 19, 17, 24, 10, 21, -23, -25,
                           21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18, -22,
                           -6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6, 10,
4,
                           2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23],
                 @ma.find([-16, -8, 9, 11, 23, -5, 15, 18, 6, -18, 21, -4,
                           -17, -19, -10, -9, 19, 17, 24, 10, 21, -23, -25,
                           21, -2, 24, -5, -4, -7, -3, -4, 16, -9, -18, -22,
                           -6, -19, 22, 18, 19, 22, -11, -3, 2, 21, 6, 10,
4,
                           2, -25, 5, -1, 20, 10, -16, 10, -2, -10, 23, -23,
16,
                           -19, -10, 12, -17, -9, 6, -8, -23, 16, -17, -10,
24,
                           -1, -6, -24, -5, 16, -11, -7, -8, 12, -21, -23,
-8,
                           -8, 4, 7, 6, -22, -8, -19, -7, 23, 4, 9, -19,
-19, 0, -15]))
    assert_equal([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9, 30, 31,
16, 44, 20, 10, 55, 28,
                  -18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17, 38,
-5, -28, 45, -38, 4,
                  4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32,
-22, 8, 37, 57, 13, 17,
                  -17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24, 34,
-10, -26, -27, 12, 5, -2,
                  4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56, 10,
-35, -29, 40, -1, 30, 45, 36],
                 @ma.find([13, 49, 23, 48, 10, 39, 20, -30, -14, 17, 26, 9,
30, 31, 16, 44, 20, 10, 55, 28,
                  -18, -30, 57, -32, -8, 5, -36, -6, -24, -39, -9, -17, 38,
-5, -28, 45, -38, 4,
                  4, 41, 35, -5, 53, 29, 1, 21, 5, -39, -6, -21, -8, 32,
-22, 8, 37, 57, 13, 17,
                  -17, 11, 18, -22, 9, -17, -26, -7, 50, -23, 30, -24, 34,
-10, -26, -27, 12, 5, -2,
                  4, 54, 23, 20, -22, -10, 36, 56, -34, 31, -2, 26, 56, 10,
-35, -29, 40, -1, 30, 45, 36, -38, 30, -28]))
  end
end

Thanks,

Justin

···

On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Harlan

Given an array of integers, find the sub-array with maximum sum. For
example:

        array: [-1, 2, 5, -1, 3, -2, 1]
        maximum sub-array: [2, 5, -1, 3]

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

15

Here's a solution which iterates over the array just once. Looks like I came up with a variant of the algorithm presented by Henrik Schmidt-Møller, though I'm storing the local max sub array rather than just its delimiting indices. I'm not happy with the calls to slice (especially as they require calculating the size of the array), but I'm pleased that I came up with a solution using recursion.

class Array
   def max_sub_array
     self.max_sub_arrayr[0]
   end

   def max_sub_arrayr
     ary = self.clone
     sub_ary = Array.new.push(ary.shift)
     sum = sub_ary[0]
     max_sub_ary = sub_ary.dup
     max_sum = sum
     done = false
     ary.each_with_index do |n,i|
       if sum > 0
         if sum + n > 0
           sum += n
           sub_ary.push(n)
         else
           sub_ary, sum = ary.slice(i+1..(ary.size-1)).max_sub_arrayr
           done = true
         end
       elsif sum <= n
         sub_ary, sum = ary.slice(i..(ary.size-1)).max_sub_arrayr
         done = true
       end
       if sum > max_sum
         max_sum = sum
         max_sub_ary = sub_ary.dup
         break if done
       end
     end
     return max_sub_ary, max_sum
   end
end

Michael Glaesemann
grzm seespotcode net

16

I see I was not the only one to borrow inspiration from Programming
Pearls. This is O(N) code... some few examples included for testing:

def max_subarray_last_index(arr)
   a = b = x = 0
   arr.each_with_index do |e, i|
      b = [b + e, 0].max
      unless a > b
         a, x = b, i
      end
   end
   return x
end

def max_subarray(arr)
   i = arr.size - max_subarray_last_index(arr.reverse) - 1
   j = max_subarray_last_index(arr)
   return arr[i..j]
end

p max_subarray( [-1, 2, 5, -1, 3, -2, 1] )
p max_subarray( [31, -41, 59, 26, -53, 58, 97, -93, -23, 84] )
p max_subarray( [] )
p max_subarray( [-10] )
p max_subarray( [10] )
p max_subarray( [-5, 5] )
p max_subarray( [5, -5] )

17

This was a nice diversion on Friday morning at the start of my kids' championship swim meet. I had to work Saturday and Sunday so the last two test cases had to wait until now (yes, I should be sleeping!).

-Rob

Rob Biedenharn http://agileconsultingllc.com
Rob@AgileConsultingLLC.com

class Array
   # Given an Array of numbers, return the contiguous sub-array having the
   # maximum sum of its elements. Longer sub-arrays are preferred.

···

#
   #--
   # (or members of any Ring having operations '+' (binary, associative and
   # commutative) and '-' (unary, giving the inverse with respect to '+'))
   #++
   def sub_max identity=0
     return self if size < 2 # nothing to sum!

     ms = Array.new(size) { Array.new(size) {identity} }
     mx, range = self[0], 0..0
     0.upto(size-1) do |e|
       e.downto(0) do |s|
         current = ms[s][e] = if s == e
                                self[s]
                              else
                                ms[s][e-1] + ms[s+1][e] + (- ms[s+1][e-1])
                              end
         if current > mx || current == mx && (e - s + 1) > (range.end - range.begin + 1)
           mx = current
           range = s..e
         end
       end
     end
     self[range]
   end
end

if __FILE__ == $0
   require 'test/unit'

   class Array
     def put2d
       print '[ '
       each do |row|
         row.put1d
         print ",\n "
       end
       puts ']'
     end

     def put1d
       print '[ '
       each do |item|
         print("%3d, " % item)
       end
       print ']'
     end
   end

   class SubMaxTest < Test::Unit::TestCase
     def test_quiz_example
       input = [-1, 2, 5, -1, 3, -2, 1]
       expected = [2, 5, -1, 3]

       assert_equal expected, input.sub_max
     end

     def test_empty
       assert_equal [], [].sub_max
     end
     def test_single
       assert_equal [ 0], [ 0].sub_max
       assert_equal [-1], [-1].sub_max
       assert_equal [ 1], [ 1].sub_max
     end
     def test_all_positive
       input = [ 1, 2, 4, 8 ]
       assert_equal input, input.sub_max
     end
     def test_all_non_negative
       input = [ 1, 2, 0, 4 ]
       assert_equal input, input.sub_max
     end
     def test_all_negative
       input = [ -1, -2, -3, -9 ]
       assert_equal [-1], input.sub_max
       input = [ -2, -1, -3, -9 ]
       assert_equal [-1], input.sub_max, 'need to test diagonal'
     end
     def test_prefer_length_earlier
       input = [ -1, 0, 1, -2, -9 ]
       assert_equal [0, 1], input.sub_max, "if actual is [1], need to add a length test on range"
     end
     def test_prefer_length_later
       input = [ -1, 1, 0, -2, -9 ]
       assert_equal [1, 0], input.sub_max, "if actual is [1], need to add a length test on range"
     end

     def test_prefer_length_multiple_options
       input = [ 1, 2, 3, -6, 6 ]
       # options
       # [6]
       # [1,2,3]
       expected = [ 1, 2, 3, -6, 6 ]
       assert_equal expected, input.sub_max, "if [6] or [1,2,3] you can do better"
     end
   end
end
__END__

18

Here's my solution to the maximum sub-array problem. I'm sure my
algorithm is not optimal, but it's readable and concise:

# file: max_sub_array.rb
# author: Drew Olson

class Array

  alias :orig_to_s :to_s

  # 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

  # pretty printing for array
  def to_s
    self.inject("[") do |str,i|
      str + "#{i}, "
    end[0...-2] + "]"
  end
end

# test example
if __FILE__ == $0
  my_arr = [-1, 2, 5, -1, 3, -2, 1]
  puts "array: #{my_arr}"
  puts "maximum sub-array: #{my_arr.max_sub_array}"
end

···

--
Posted via http://www.ruby-forum.com/.

19

Solution #1: Array is bound to arr
   
  sub_arrs = []
arr.each_index{|i| (i...arr.length).each{|i2| sub_arrs << arr[i..i2]}}
p sub_arrs.sort_by{|arr| arr.inject(0){|s,n|s+n}}.last
   
  Solution #2: Array is bound to a
   
  p (b=(0...(l=a.size)).to_a).zip([b]*l).map{|(i,s)|s.map{|j|a[i,j]}}.sort_by{|a|a.map!{|a|[a.inject(0){|s,n|s+n},a]}.sort![-1][0]}[-1][-1][-1]

···

---------------------------------
Now that's room service! Choose from over 150,000 hotels
in 45,000 destinations on Yahoo! Travel to find your fit.

20

Extra Credit:

Given a matrix of integers, find the rectangle with maximum sum.

···

On 7/13/07, Ruby Quiz <james@grayproductions.net> wrote:
#
# This is roughly the same matrix solution I posted before.
# Sorry for the double post. Two lines in the middle of the program were
# too long and got wrapped in the post.
# I made the lines shorter and tried again.
#
# Here is my matrix solution.
# It does the Matrix extra credit.
# If there are multiple rectangles that equal max sum, it prints all of them.
#
# Since the quiz did not specify how to input,
# I just hard coded a sample Matrix at the beginning.

require 'matrix'
mat=Matrix[[7,-1,2,3,-4],[-7,8,-22,10,11],[3,15,16,17,-18],[4,22,-23,-24,-25]]
s =
(0...mat.row_size).each do |a|
  (0...mat.column_size).each do |b|
    (1..mat.row_size).each do |x|
      (1..mat.column_size).each do |y|
      s << mat.minor(a,x,b,y)
      end
    end
  end
end

tot = s.uniq.map {|x| x.to_a}
bg=tot.max{|x,y|x.flatten.inject(0){|a,b|a+b}<=>y.flatten.inject(0){|c,d|c+d}}
sb=tot.select{|r|r.flatten.inject(0){|a,b|a+b}==bg.flatten.inject(0){|c,d|c+d}}
puts "Original Matrix"
(0...mat.row_size).each do |x|
print mat.row(x).to_a.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"
end
puts
puts "Solutions"
sb.each do |x|
puts
  x.each {|y| print y.map{|m| m.to_s.rjust(tot.flatten.max.to_s.length+2)},"\n"}
end

# Harry

--
A Look into Japanese Ruby List in English