Maximum Sub-Array (#131)

Given that the spoiler time is finished (I think) these are my
solutions to the Quiz #131. I only worked on single arrays (and not
matrixes). If found 3 different solutions. The first one just searches
through the solution space and calculates the value for each subarray.
It takes O(n^3). The second one uses that the sum is associative to
use the previous calculation for the sum of a subarray to decrese the
time complexity to O(n^2). And, in the end, I’ve found a way to find
the max sub array in a single pass O(n). All the solutions have
constant space constraints (O(1)).

Here is the code (also at http://pastie.caboo.se/78970):
#!/usr/bin/env ruby

class Array

Runs in O(n^3), change the value function and find using any

objective function.
def max_subarray_original

better_subarray = []
better_value = 0
(0...self.length).each do |start|
  (start...self.length).each do |finish|
    value = value(start, finish)
    if (value > better_value) then
      better_value = value
      better_subarray = self[start..finish]
    end
  end
end

better_subarray

end

def value(start, finish)
self[start…finish].inject(0) { |acum, value| acum+value }
end

Runs in O(n^2), uses the sum asociativity to avoid an iteration

through the array.
def max_subarray_optimized

better_subarray = []
better_value = 0
(0...self.length).each do |start|
  value = 0
  (start...self.length).each do |finish|
    value += self[finish]
    if (value > better_value) then
      better_value = value
      better_subarray = self[start..finish]
    end
  end
end

better_subarray

end

It’s technically imposible to improve it in time or space

complexity.

Runs in O(n) time and O(1) space*.

* Assumes that each number takes the same space in memory and that

additions, substractions and comparisions take constant time.
def max_subarray_single_pass

sum = 0
min_pos = -1
min_value = 0
min_pos_at_left = -1
min_value_at_left = 0
better_end_pos = -1
better_value = 0

self.each_with_index do
  |value, index|
  sum += value
  if sum - min_value > better_value then
    better_value = sum - min_value
    better_end_pos = index
    min_value_at_left = min_value
    min_pos_at_left = min_pos
  end
  if sum < min_value then
    min_value = sum
    min_pos = index
  end
end

return [] if better_end_pos == -1
return self[(min_pos+1)..better_end_pos]

end
end

some manual testing

[[-1, 2, 5, -1, 3, -2, 1],
[1, -1000, 100],
[-3, -2, -1]].each do
|array|

puts “array”
p array

puts “max_subarray_original”
p array.max_subarray_original

puts “max_subarray_optimized”
p array.max_subarray_optimized

puts “max_subarray_single_pass”
p array.max_subarray_single_pass
end

On Sun, 15 Jul 2007 21:30:59 +0900, Aureliano C. wrote:

Given that the spoiler time is finished (I think) these are my
solutions to the Quiz #131.

And here is mine, which I think it’s the same of your solution #3.

If I understand the problem correctly this is a known problem and
finding the optimal solution is a classic example of Dynamic Programming
(where programming = planning, no relation with eval & duck typing).

But I solved it some time ago with TDD finding an cool case
where test-first finds an optimal algorithm, so it may be interesting to
report it. Notice that I start finding the maximum subsequence value,
well’keep track of the indexes later.

#max.rb, step 1. I use variable length arguments instead of array
objects.

if FILE == $0
require ‘test/unit’
class TC < Test::Unit::TestCase
alias is assert_equal
def test_maxseq
is 0, maxseq(0)
end
end
end

ok, test fails cause no maxseq exists, yet

step 2

def maxseq(*ary)
total=0
end

passes, step 3:

def test_maxseq
is 0, maxseq(0)
is 3, maxseq(0,1,2)
end

fails, we need a sum:

def maxseq(*ary)
total=0
ary.each {|el| total+=el}
total
end

ok now passes again, try with a negative number:

def test_maxseq
is 0, maxseq(0)
is 3, maxseq(0,1,2)
is 0, maxseq(-1), “we choose 0 if we have only negative values”
end

return 0 if adding means getting a smaller result

def maxseq(*ary)
total=0
ary.each {|el| total=[total+el,0].max}
total
end

ok, passes again, let’s add some more complex sequences:

  is 6, maxseq(1,2,3)
  is 3, maxseq(1,-2,3)
  is 3, maxseq(1,2,-3)

mh… the last fails, because we return 0… we should keep the

current value, which will be zero at the beginning:

def maxseq(*args)
total=0
current=0
args.each do |el|
current=[current+el,0].max
total=[total,current].max
end
total
end

now let’s throw some more stuff at it:

def test_maxseq
  is 0, maxseq(0)
  is 3, maxseq(0,1,2)
  is 0, maxseq(-1), "we choose [] if we have only negative values"
  is 6, maxseq(1,2,3)
  is 3, maxseq(1,-2,3)
  is 3, maxseq(1,2,-3)
  is 3, maxseq(1,2,-3)
  is 5, maxseq(-1,2,3)
  is 0, maxseq(-1,-2)
  is 8, maxseq(1,-2,3,4,-5,6,-7)
  is 6, maxseq(1,-2,-3,6)
  is 11,maxseq(0,1,-2,-3,5,6)
end

And then you realize… well, it works, no need for complications, and it
runs in linear time, which is pretty good, compared to the naive
approach
of trying all possible subsequences.

Now, to make it a dirty oneliner:
def maxseq(*ary)
ary.inject([0, 0]) {|(t, c), e| [[t, c=[c+e, 0].max].max, c]}.first
end

and all tests still pass :slight_smile:

By this point it is trivial to keep track of the indexes:

def maxseq_indexes(*args)

total now means “total value, where they start, where they finish”

total = start = finish = 0

current too

current = curr_start = curr_finish =0
args.each_with_index do |el,idx|
if current+el >= 0
current+=el
curr_finish = idx
else
current = 0
curr_start = idx+1
end
if current >= total
total = current
start = curr_start
finish = curr_finish
end
end
total.zero? ? [] : args[start…finish]
end

and its tests:
def test_maxseq_indexes2
is [], maxseq_indexes(0)
is [0,1,2], maxseq_indexes(0,1,2)
is [], maxseq_indexes(-1), “we choose [] if we have only negative
values”
is [1,2,3], maxseq_indexes(1,2,3)
is [3], maxseq_indexes(1,-2,3)
is [1,2], maxseq_indexes(1,2,-3)
is [2,3], maxseq_indexes(-1,2,3)
is [], maxseq_indexes(-1,-2)
is [3,4,-5,6], maxseq_indexes(1,-2,3,4,-5,6,-7)
is [6], maxseq_indexes(1,-2,-3,6)
is [5,6],maxseq_indexes(0,1,-2,-3,5,6)
is [2,5,-1,3], maxseq_indexes(-1, 2, 5, -1, 3, -2, 1)
end

I’m quite sure it can be made a oneliner again, but I am busy :slight_smile:

sender: “Aureliano C.” date: “Sun, Jul 15, 2007 at 09:30:59PM +0900” <<<EOQ
Hi all,

Given that the spoiler time is finished (I think) these are my
solutions to the Quiz #131. I only worked on single arrays (and not
matrixes). If found 3 different solutions. The first one just searches
through the solution space and calculates the value for each subarray.
It takes O(n^3). The second one uses that the sum is associative to
use the previous calculation for the sum of a subarray to decrese the
time complexity to O(n^2). And, in the end, I’ve found a way to find
the max sub array in a single pass O(n).
The last solution has a bug:

$ ruby sol.rb
array
[-28, -11, -6, -35, 42, 17, 93, -92, -39, 79, -87, -25, -85, 26, 84, 9,
89, -79, 9, 42, -38, 1, -17, -23, 2, -100, -64, 5, 44, -23, -61, 28,
-53, 9, 20, -45, -58, 81, -13, -3, 26, -76, 73, -99, -61, 76, -34, -64,
-40, 98, 68, -49, -53, -81, -27, 11, 42, 57, 19, 30, -90, 62, 23, -91,
-98, -93, 88, -92, -5, -59, -76, 48, -2, 59, -75, -86, -68, 57, 31, 7,
-2, 7, 15, 9, -63, 89, -16, 94, -12, -90, -20, -96, -82, -6, -5, 46, 25,
-27, 16, 50]
max_subarray_original
[57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94]
max_subarray_optimized
[57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94]
max_subarray_single_pass
[]

Cheers,
Alex

On 7/15/07, Aureliano C. [email protected] wrote:

$ ruby sol.rb
max_subarray_optimized

  sum += value
end

return [] if better_end_pos == -1
return self[(min_pos_at_left+1)..better_end_pos] # changed min_pos

with min_pos_at_left
end
end

I’ve forgotten to tell that the corrected solution is at
http://pastie.caboo.se/78975

$ ruby sol.rb
max_subarray_optimized
[57, 31, 7, -2, 7, 15, 9, -63, 89, -16, 94]
max_subarray_single_pass
[]

You’re right!!!
It has a bug in the last line :-(. Here is the corrected solution
(which passes your test).

class Array
def max_subarray_single_pass

sum = 0
min_pos = -1
min_value = 0
min_pos_at_left = -1
min_value_at_left = 0
better_end_pos = -1
better_value = 0

self.each_with_index do
  |value, index|
  sum += value
  if sum - min_value > better_value then
    better_value = sum - min_value
    better_end_pos = index
    min_value_at_left = min_value
    min_pos_at_left = min_pos
  end
  if sum < min_value then
    min_value = sum
    min_pos = index
  end
end

return [] if better_end_pos == -1
return self[(min_pos_at_left+1)..better_end_pos] # changed min_pos

with min_pos_at_left
end
end

Here is a O(n) solution. This simply finds the max accumulation minus
the min accumulation. I haven’t done too much testing, so I don’t
know if it handles all of the corner cases.

def max_subarray(seq)
max_sum = 0
min_sum = 0
max_i = -1
min_i = -1
sum = 0
seq.each_with_index { |val,i|
sum += val
if sum>max_sum
max_sum = sum
max_i = i
end
if sum<min_sum
min_sum = sum
min_i = i
end
}
if min_i>max_i
min_sum = 0
min_i = -1
end
seq[(min_i+1)…(max_i+1)]
end

Here’s my solution. Nothing fancy. It finds the maximum subarray of
the shortest length.

class Array

def sum
inject{ |s,v| s + v }
end

def subarrays
size.times{ |f| 1.upto(size - f){ |l| yield self[f,l] } }
end

def max_sum
results = Hash.new{|h,k| h[k] = [] }
subarrays{ |a| results[a.sum] << a }
results.max.last.min
end

end

p ARGV.map{ |i| i.to_i }.max_sum if FILE == $PROGRAM_NAME

On Jul 15, 2007, at 7:30 AM, Aureliano C. wrote:

Given that the spoiler time is finished (I think) these are my
solutions to the Quiz #131.

When I first considered this quiz, I tried to whipped up a quick and
dirty brute force solution:

#!/usr/bin/env ruby -wKU

array = [-1, 2, 3, -1, 2]
answer = (0…array.size).inject(Array.new) do |sub_arrs, i|
sub_arrs.push(*(1…(array.size - i)).map { |j| array[i, j] })
end.map { |sub| [sub.inject(0) { |sum, n| sum + n }, sub] }.max.last

p answer

END

I resolved it yesterday using a linear dynamic programming algorithm:

#!/usr/bin/env ruby -wKU

class Array
def max_subarray
sum, start, length = self[0], 0, 1
best_sum, best_start, best_length = sum, start, length

 each_with_index do |n, i|
   sum, start, length = 0, i, 0 if sum < 0

   sum    += n
   length += 1

   best_sum, best_start, best_length = sum, start, length if sum

best_sum
end

 self[best_start, best_length]

end
end

if FILE == $PROGRAM_NAME
if ARGV.empty?
require “test/unit”

 class TestMaxSubarray < Test::Unit::TestCase
   def test_single_element
     -1.upto(1) { |n| assert_equal(Array(n), Array

(n).max_subarray) }
end

   def test_all_positive
     assert_equal([1, 2, 3], [1, 2, 3].max_subarray)
   end

   def test_all_negative
     assert_equal([-1], [-3, -2, -1].max_subarray)
   end

   def test_quiz_example
     assert_equal([2, 5, -1, 3], [-1, 2, 5, -1, 3, -2,

1].max_subarray)
end
end
else
p ARGV.map { |n| Integer(n) }.max_subarray
end
end

END

James Edward G. II

On 7/15/07, Jesse M. [email protected] wrote:

=> [-2, 0, 0, 4, -5, 1]
irb(main):053:0> max_subarray arr
=> [-2, 0, 0, 4]

Thanks for pointing out my mistake. I didn’t handle the case when the
min accumulation comes after the max accumulation very well. Now it
records the min index when it finds the best sub-array sum so far
(instead of blindly subtracting min from max at the end). Here is a
corrected version w/ some testing in irb:

def max_subarray(seq)
min_sum = 0
min_i = -1
max_delta = 0
max_i = -1
max_i0 = -1
sum = 0
seq.each_with_index { |val,i|
sum += val
delta = sum-min_sum
if delta>max_delta
max_delta = delta
max_i = i
max_i0 = min_i
end
if sum<min_sum
min_sum = sum
min_i = i
end
}
seq[(max_i0+1)…(max_i+1)]
end

irb(main):001:0> require ‘quiz131’
=> true
irb(main):002:0> max_subarray([-1, 2, 5, -1, 3, -2, 1])
=> [2, 5, -1, 3]
irb(main):003:0> max_subarray([-2,0,0,4,-5,1])
=> [0, 0, 4]
irb(main):004:0> max_subarray([-1, 2, 5, -1, 3, -2, 1])
=> [2, 5, -1, 3]
irb(main):005:0> max_subarray([31, -41, 59, 26, -53, 58, 97, -93, -23,
84] )
=> [59, 26, -53, 58, 97]
irb(main):006:0> max_subarray([])
=> []
irb(main):007:0> max_subarray([-10] )
=> []
irb(main):008:0> max_subarray([10])
=> [10]
irb(main):009:0> max_subarray([-5, 5])
=> [5]
irb(main):010:0> max_subarray([5, -5])
=> [5]

On Sunday 15 July 2007 15:18, Eric M. wrote:

Here is a O(n) solution. This simply finds the max accumulation minus
the min accumulation. I haven’t done too much testing, so I don’t
know if it handles all of the corner cases.

FYI, your solution does indeed fail in some cases:

irb(main):052:0> arr = [-2,0,0,4,-5,1]
=> [-2, 0, 0, 4, -5, 1]
irb(main):053:0> max_subarray arr
=> [-2, 0, 0, 4]