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

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