Rubyタイムアウトで実行される最大連続連続サブアレイの効率的なアルゴリズム

Question

RubyのInterviewbitで最大連続連続サブアレイの問題を解決しました。問題は次のとおりです。

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. 

私が使用したアルゴリズムは、この問題を解決する最も効率的な方法の1つだと思います。しかし、私は 'タイムリミット超過'を取得します。意外にも、Pythonで実装された同じアルゴリズムが受け入れられます。以下は、アルゴリズムのルビーとPythonのバージョンです。ルビ実装の問題は何でしょうか？ 。助けてください。ありがとう。

ルビー

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] > curr_max+a[i]) ? a[i] : curr_max+a[i] 
       max_so_far = (max_so_far > curr_max) ? max_so_far : curr_max 
      end 

      max_so_far 

    end 

Pythonの

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 

Answer 1

Rubyはおそらくjust objectively slower at some tasksです。 forループの別の種類、つまりInteger#timesを試したいかもしれませんが、それはあまりにも遅すぎるかもしれません。

Answer 2

Pythonコードは、配列の要素を直接ループします。 Rubyコードはこれらの要素をインデックスで3回アクセスします。 Pythonと同じようにRubyコードを変更すると、コードは約70％高速になります。

def maxSubArray2(ar) 
    curr_max = max_so_far = ar[0] 
    for x in ar 
    curr_max = (x > curr_max+x) ? x : curr_max + x 
    max_so_far = curr_max if curr_max > max_so_far 
    end 
    max_so_far 
end