On 7/15/07, Aureliano Calvo <aurelianocalvo / gmail.com> wrote:
> > > 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