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

On Jul 13, 2007, at 2:29 PM, Ari Brown wrote:

> Being a nub at life, liberty, and ruby, what is the best way to  
> search it? Would it be to go and sum up the elements in every  
> possible array (ie, [abc] => [a]. [b]. [c]. [ab]. [bc])? Because  
> that seems like it would get very CPU consuming with larger arrays.

An exhaustive search would have execution time on the order of N**2,  
where N is the length of the array. That's not great but its not  
horrible either -- that is, not nearly so bad as a search that takes  
exponential (e**N) time.

Regards, Morton