[QUIZ] Maximum Sub-Array (#131)

ruby-talk
21

this is my first entry
(only found this place last week)

so it's late,
but I like it.

I deal with left-subarrays, and right-subarrays
(i decided that intuitively a max sub array is a max left of a max
right,
but have not the time to prove this)
I also assume that the empty array [] is always a member.

also, my max_left_of_right and max_right_of_left methods will return
multiple copies of the empty array if that is indeed the smallest.

I did initially uniq the result,
but decided against it in the end
(who says that the empty array is a unique sub array -- probably me)

class Array

  # solution 1
  def max_subs
    max_found, max_instances = 0, [[]] # the empty sub array will
always return 0 sum
    self.left_subs.each do |l_sub|
      next if l_sub.last.nil? || l_sub.last < 0 # if
      l_sub.right_subs.each do |sub|
        next if sub.first.nil? || sub.first < 0
        if (sub_sum = sub.sum) > max_found
          max_found, max_instances = sub_sum, [sub]
        elsif sub_sum == max_found
          max_instances << sub
        end
      end
    end
    return max_instances
  end

  # i hypothesise that each max sub array is actually;
  # a max left sub of a max right sub, and the other way round
  # but i dont have time to prove it

  # solutions 2 and 3
  def max_left_of_right
      max_right_subs.inject([]){|rtn, max_r| rtn + max_r.max_left_subs}
  end

  def max_right_of_left
      max_left_subs.inject([]){|rtn, max_l| rtn + max_l.max_right_subs}
  end

  # sub methods

  def left_subs
    if (l_sub = self.dup) && l_sub.pop
      return (l_sub.left_subs << self.dup)
    else
      return [self]
  end
  end

  def right_subs
    if (r_sub = self.dup) && r_sub.shift
      return (r_sub.right_subs << self.dup)
    else
      return [self]
  end
  end

  def sum
    self.inject(0){|sum, element| sum+element}
  end

  def max_left_subs
    max_of_subs(:left_subs)
  end

  def max_right_subs
    max_of_subs(:right_subs)
  end

  def max_of_subs(method)
    max_found, max_instances = 0, [[]] # we expect to have an empty sub
    self.send(method).each do |sub|
      if (sub_sum = sub.sum) > max_found
        max_found, max_instances = sub_sum, [sub]
      elsif sub_sum == max_found
        max_instances << sub
      end
    end
    return max_instances
  end
end

···

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

22

Oh, these quizzes. I need to either find more time to play with them
or stop telling myself I don't have the time. I did this in Perl for
a job interview a while ago and happened to still have it handy, so
all I did was translate it (somewhat) into Ruby.

···

-------------------------------------------------------------------------------
class Array
  def largest_sum_sequence
    # initialize with a sequence of the first number
    largest = {
      :sum => first,
      :start => 0,
      :end => 0
    }

    (0 .. length-1).each do |start_i|
      sum = 0
      start_num = self[start_i]

      # don't bother with a sequence that starts with a negative number
      # but what if all the numbers are negative?
      next if largest[:sum] > start_num and start_num < 0

      (start_i .. length-1).each do |end_i|
        end_num = self[end_i]
        sum += end_num

        # if this sequence is the largest so far
        if sum > largest[:sum]
          largest[:sum] = sum
          largest[:start] = start_i
          largest[:end] = end_i
        end
      end
    end

    puts "Largest sum: #{largest[:sum]}"
    puts "The sequence starts at element #{largest[:start]} and goes to
element #{largest[:end]}"
    puts "The sequence is #{self[largest[:start] ..
largest[:end]].join(' ')}"
  end
end

numbers = ARGV.collect { |arg| arg.to_i }

numbers.largest_sum_sequence
-------------------------------------------------------------------------------

--
-yossef

23

Duh. Nevermind :slight_smile: Maximum sub *array*. I get it. Carry on. Don't mind me...

Matt

···

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> 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]

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

[2, 5, 3] ?

24

Let's say we are looking for a non-empty subarray.

James Edward Gray II

···

On Jul 13, 2007, at 10:42 AM, Paul Novak wrote:

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.

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

25

Morton Goldberg wrote, On 7/15/2007 10:44 AM:

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 }
         

Doesn't this basically make it order n cubed?

···

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

26

Not to be the downer who points out everyone's problems, but here's a bug:

irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19, -36, -6,
                      -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, 37, 39,
                      -22, 11, -44, -40, -37, -26]
irb(main):009:0> arr.max_sub_array
=> [37, 39, 10]

That sequence does not appear in arr.

···

On Sunday 15 July 2007 17:17, Michael Glaesemann wrote:

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.

<snip>

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

27

A late late entry (I was busy yesterday).
Yes it does an exhaustive search, but for even moderate sized sets,
it's feasibly fast enough.

class Array
  def sum()
    s=0
    each{|i| s+=i}
    s
  end
end

array=[-6,-5,-4,-3,-2,-1,0,1,2,3,-5,4,5,6]
maxIndex = array.length-1
sizeByRange = {}
0.upto(maxIndex) do
  >start>
  start.upto(maxIndex) do
    >endI>
    sizeByRange.store(array[start..endI].sum,start..endI)
    #puts "subarray #{start} to #{endI} sums to #{array[start..endI].sum}"
  end
end

puts "Minimum array is [#{array[sizeByRange.min[1]].join(',')}]"
puts "Maximum array is [#{array[sizeByRange.max[1]].join(',')}]"

28

Just a note on my "solution" I sent in earlier... Well, it's not
entirely correct... I've been shown at least one case that fails.
It's probably not that far off, but unfortunately I don't have time
this week to correct it... Just so no summaries go using it.

29

What are the criteria for selecting from multiple possibilities? For example:

[1,2,3,-7,6]

options:

[1,2,3]
[6]

Does it matter?

···

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> 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]

30

Yes, the inject introduces another factor of N. I missed that.

Regards, Morton

···

On Jul 15, 2007, at 1:47 PM, Sammy Larbi wrote:

Morton Goldberg wrote, On 7/15/2007 10:44 AM:

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 }

Doesn't this basically make it order n cubed?

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>

31

Not to be the downer who points out everyone's problems, but here's a bug:

No problem at all! Thanks for taking a look at my work :slight_smile:

irb(main):008:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19, -36, -6,
                      -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, 37, 39,
                      -22, 11, -44, -40, -37, -26]
irb(main):009:0> arr.max_sub_array
=> [37, 39, 10]

This should be a bit more pleasing :slight_smile:

irb(main):002:0> arr = [46, -8, 43, -38, -34, -14, 10, -26, -9, -19, -36, -6,
                            -20, -4, -23, -25, 48, -22, 22, 5, -21, -33, 37, 39,
                            -22, 11, -44, -40, -37, -26]
irb(main):005:0> arr.max_sub_array
=> [46, -8, 43]

Updated code follows below signature:

Michael Glaesemann
grzm seespotcode net

class Array
   def max_sub_array
     return if self.empty?
     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.dup.slice(i..(ary.size-1)).max_sub_arrayr
           done = true
         end
       elsif sum <= n
         sub_ary, sum = ary.dup.slice(i..(ary.size-1)).max_sub_arrayr
         done = true
       end
       if sum > max_sum
         max_sum = sum
         max_sub_ary = sub_ary.dup
       end
       break if done
     end
     return max_sub_ary, max_sum
   end
end

···

On Jul 15, 2007, at 20:19 , Jesse Merriman wrote:

32

Next week's quiz: debug Matthew's solution. :wink:

James Edward Gray II

···

On Jul 17, 2007, at 11:12 AM, Matthew Moss wrote:

Just a note on my "solution" I sent in earlier... Well, it's not
entirely correct... I've been shown at least one case that fails.
It's probably not that far off, but unfortunately I don't have time
this week to correct it... Just so no summaries go using it.

33

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

What are the criteria for selecting from multiple possibilities? For example:

[1,2,3,-7,6]

Or this:

[1,2,3,-6,6]

options

[1,2,3]
[1,2,3,-6,6]
[6]

···

On 7/13/07, David Chelimsky <dchelimsky@gmail.com> wrote:

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:
> On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:

options:

[1,2,3]
[6]

Does it matter?

34

I think either selection would be acceptable. I would probably favor the shorter one, but I don't think it matters.

James Edward Gray II

···

On Jul 13, 2007, at 10:56 AM, David Chelimsky wrote:

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> wrote:

On 7/13/07, Matt Greer <matt.e.greer@gmail.com> 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]

What are the criteria for selecting from multiple possibilities? For example:

[1,2,3,-7,6]

options:

[1,2,3]
[6]

Does it matter?

35

Eh.... I got some better quizzes in mind than debugging my lousy
code... I just have to write them up. (This thing called "day job"
keeps getting in the way...)

···

On 7/17/07, James Edward Gray II <james@grayproductions.net> wrote:

On Jul 17, 2007, at 11:12 AM, Matthew Moss wrote:

> Just a note on my "solution" I sent in earlier... Well, it's not
> entirely correct... I've been shown at least one case that fails.
> It's probably not that far off, but unfortunately I don't have time
> this week to correct it... Just so no summaries go using it.

Next week's quiz: debug Matthew's solution. :wink:

James Edward Gray II

36

Am I missing something, or is this one of the easiest quizzes that's
been put forward?

--Kyle

37

could someone explain this please? I really don't understand this quiz?

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]

I know what an array is :slight_smile: I know what integers are :slight_smile: I know what a sum is :slight_smile:

but why is [2, 5, -1, 3] sum= 9 the sub-array with the maximum sum? wouldn't be [2,5,3,1] sum=11 the right solution?

···

--
greets

                     one must still have chaos in oneself to be able to give birth to a dancing star

38

I always enjoy your quizzes Matthew. Looking forward to it.

James Edward Gray II

···

On Jul 18, 2007, at 9:17 AM, Matthew Moss wrote:

Eh.... I got some better quizzes in mind than debugging my lousy
code... I just have to write them up. (This thing called "day job"
keeps getting in the way...)

39

Am I missing something, or is this one of the easiest quizzes that's
been put forward?

Well, you're missing the fizzfuzz quiz.

40

It's a pretty easy problem. I almost rejected it for that reason.

I was just sure I could do it with a one-liner, but when my own solution didn't make it down to that I accepted the problem. I'm sure someone will get it down there, but I didn't so it required a touch more thought than I expected.

We've had some pretty easy problems. FizzBuzz was pretty close to this level.

I'm fine with that thought. Ruby Quiz is for all levels.

James Edward Gray II

···

On Jul 13, 2007, at 11:10 AM, Kyle Schmitt wrote:

Am I missing something, or is this one of the easiest quizzes that's
been put forward?