Alexandru E. Ungur
7/15/2007 1:39:00 PM
>>> sender: "Aureliano Calvo" 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