2

私は次のコードを書いて、最大合計で連続した部分配列を見つけましたが、これはかなり醜いと思います。

問題は、この問題に対する私の内部的な考え方 (DP を使用) が不可欠であることです。このコードをリファクタリングして、より機能的に (そして DRY に) するにはどうすればよいでしょうか? 関数型言語でアルゴリズムを考える方法に関する推奨事項はありますか? （たぶん、別の質問になるはずです）。

class Object
  def sum(lst)
    lst.reduce(:+)
  end
end

def dp_max_subarray(lst)
  i=0
  s=0
  while i<lst.length
    (i...lst.length).each do |j|
      t = sum lst[i..j]
      if t > s
        s= sum lst[i..j]
        next
      elsif t < 0
        i=j+1
        break
      end
    end
    i+=1
  end
  s
end
4

2 に答える 2

2

私はこれをワンライナーにした（しかし、効率的ではなく、まったく読めない）：

(0...arr.length).map{|start| (1..(arr.length-start)).map{|length| arr.slice(start, length).inject(:+)}.max}.max
于 2012-08-08T18:56:55.310 に答える
2

O(n) Python ソリューションについては、こちらをご覧ください。これを関数型 Rub​​y に変換するのは簡単です。

def max_subarray(xs)
  xs.inject([0, 0]) do |(max_so_far, max_up_to_here), x|
    new_max_up_to_here = [max_up_to_here + x, 0].max
    new_max_so_far = [max_so_far, new_max_up_to_here].max
    [new_max_so_far, new_max_up_to_here]
  end.first
end

xs = [31, -41, 59, 26, -53, 58, 97, -93, -23, 84]
max_subarray(xs) #=> 187
于 2012-08-08T18:45:45.823 に答える