From: Sammy Larbi <sam@...>
Date: 2007-07-16T02:47:05+09:00
Subject: Re: [QUIZ] Maximum Sub-Array (#131)

Morton Goldberg wrote, On 7/15/2007 10:44 AM:
> My solution to Quiz 131. It does a straight-forward O(N**2) search. I 
> did add a constraint: the algorithm should return a sub-array of 
> minimal length. This is because I strongly prefer [0] to [0, 0, 0, 0, 
> 0, 0, 0].
>
> My submission also shows my preference for code that is 
> readable/maintainable rather than golfed/obfuscated. (This is not 
> intended as a shot at those who enjoy code golf -- I'm just saying 
> it's not for me.)
>
> <code>
> # Return the non-empty sub-array of minimal length that maximizes the sum
> # of its elements.
> def max_sub_array(arry)
>    max_sum = arry.inject { |sum, n| sum += n }
>    min_length = arry.size
>    result = arry
>    (1...arry.size).each do |i|
>       (i...arry.size).each do |j|
>          sub = arry[i..j]
>          sum = sub.inject { |sum, n| sum += n }
>          
Doesn't this basically make it order n cubed?


> next if sum < max_sum
>          next if sum == max_sum && sub.size >= min_length
>          max_sum, min_length, result = sum, sub.size, sub
>       end
>    end
>    result
> end
> </code>
>
> Regards, Morton
>
>
>