From: Morton Goldberg <m_goldberg@...>
Date: 2007-07-16T10:08:16+09:00
Subject: Re: [QUIZ] Maximum Sub-Array (#131)

On Jul 15, 2007, at 1:47 PM, Sammy Larbi wrote:

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

Yes, the inject introduces another factor of N. I missed that.

Regards, Morton