[QUIZ-Solution] Maximum Sub-Array (#131)

[Aureliano Calvo]

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

 

[gabriele renzi]

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

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

 

[Alexandru E. Ungur]

sender: "Aureliano Calvo" 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

 

[Aureliano Calvo]

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

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

 

[Aureliano Calvo]

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

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

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

 

[James Edward Gray II]

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

 

[Eric Mahurin]

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

 

[Gordon Thiesfeld]

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

 

[Jesse Merriman]

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.

<snip>

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]

 

[Eric Mahurin]

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.

<snip>

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]

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]