# 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 Parked at Loopia):
#!/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

complexity.

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

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

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

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

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]