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