# Max contiguous slice in Ruby

I need to compute the max contiguous slice in an array. I wrote this function, but I am not sure if it is correct or I am missing edge cases. I ran several cases.

def max_slice(a)
max_start,max_end = 0,0
largest_sum = 0
curr_start,curr_end = 0,0
curr_sum = 0
for i in 0..a.length-1
if (curr_sum + a[i]  < 0 ) then
curr_start = i+1
curr_sum = 0
elsif (curr_sum + a[i] > curr_sum) then
curr_sum = curr_sum + a[i]
curr_end = i
if (curr_sum > largest_sum) then
max_start, max_end = curr_start,curr_end
largest_sum = curr_sum
end
end
end
a[max_start..max_end]
end

p max_slice([-3,39,2,-1,65]) #> [39, 2, -1, 65]
p max_slice([12,-3,39,2,-1,65]) #> [12, -3, 39, 2, -1, 65]
p max_slice([]) #> []
p max_slice([2,3]) #> [2, 3]
p max_slice([-2,3]) #> 
p max_slice([-2]) #> [-2]
p max_slice([12,-3,39,2,-1,102]) #> [12, -3, 39, 2, -1, 102]
p max_slice([-5,-3,39,2,-39,65]) #> [39, 2, -39, 65]
p max_slice([-5,5,39,2,-60,65]) #> 
p max_slice([-5,35,39,2,-60,65]) #> [35, 39, 2, -60, 65]
p max_slice([-5,35,39,2,-160,65]) #> [35, 39, 2]

• I'm voting to put this on hold until you've properly tested the code. If you're unsure it's correct, then the code isn't ready to be reviewed. – RubberDuck Aug 8 '15 at 11:25
• @RubberDuck I would leave it open as "works to the best of OP's knowledge". Sometimes you're pretty sure it works, know there might be some missing edge cases, but can't find any problematic one. Well all know that there can't always be a full covergae in the testsuite. – Morwenn Aug 8 '15 at 12:40
• @Morwenn this sounds very unsure to me. I agree with Ducky here. – Vogel612 Aug 10 '15 at 9:33

What you are doing here is Kadane's algorithm. Wikipedia presents an implementation in Python which should not be hard to rewrite in Ruby.

Instead of writing a method that takes the array as a parameter, you may want to take advantage of Ruby Open Classes and add the method to the Array class so that it can operate on itself:

Class Array
def max_slice
max_start,max_end = 0,0
largest_sum = 0
curr_start,curr_end = 0,0
curr_sum = 0
for i in 0..self.length-1
if (curr_sum + self[i]  < 0 ) then
curr_start = i+1
curr_sum = 0
elsif (curr_sum + self[i] > curr_sum) then
curr_sum = curr_sum + self[i]
curr_end = i
if (curr_sum > largest_sum) then
max_start, max_end = curr_start,curr_end
largest_sum = curr_sum
end
end
end
self[max_start..max_end]
end
end


Now you can do this:

p [-3,39,2,-1,65].max_slice #> [39, 2, -1, 65]


or

arr = [-5,5,39,2,-60,65]
p arr.max_slice #> 


I would modularize the code:

class Array
def contiguos_slices
# Exercise for the reader (or you may find an implementation at StackOverlow)
end

def sum
self.inject(0, :+)
end

end

p [1,2,-3,4].contiguos_slices.max_by(&:sum)