title: Efficient algorithm for maximum sum contiguous subarray implemented in ruby times out
body: <p>I solved the maximum sum contiguous subarray problem on Interviewbit in Ruby. The problem is as follows:</p>
  
  <pre><code>Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
  
  For example:
  
  Given the array [-2,1,-3,4,-1,2,1,-5,4],
  
  the contiguous subarray [4,-1,2,1] has the largest sum = 6.
  
  For this problem, return the maximum sum.
  </code></pre>
  
  <p>The algorithm i used is i think one of the most efficient ones to solve this problem. However i get a 'Time Limit Exceeded' . Surprisingly the same algorithm implemented in Python gets accepted !.  Below are the ruby and python versions of the algorithm. What could be the problem with the ruby implementation ? . Please help. Thanks.</p>
  
  <p><strong>Ruby</strong></p>
  
  <pre><code> def maxSubArray(a)
              max_so_far = a[0]
              curr_max = a[0]
              arr_size = a.size
  
              for i in 1...arr_size
                  curr_max = (a[i] &gt; curr_max+a[i]) ? a[i] : curr_max+a[i]
                  max_so_far = (max_so_far &gt; curr_max) ? max_so_far : curr_max 
              end
  
              max_so_far
  
      end
  </code></pre>
  
  <p><strong>Python</strong></p>
  
  <pre><code>def maxSubArray(self, A):
          max_ending_here = max_so_far = A[0]
          for x in A[1:]:
              max_ending_here = max(x, max_ending_here+x)
              max_so_far = max(max_so_far, max_ending_here)
          return max_so_far
  </code></pre>