3
\$\begingroup\$

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]) #> [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]) #> [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]
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – RubberDuck Aug 8 '15 at 11:25
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Morwenn Aug 8 '15 at 12:40
  • \$\begingroup\$ @Morwenn this sounds very unsure to me. I agree with Ducky here. \$\endgroup\$ – Vogel612 Aug 10 '15 at 9:33
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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 #> [65]
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.