ruby - 如何在 ruby​​ 中使用函数式编程范式重写在动态编程中查找最大连续子数组？

Question

我编写了以下代码来查找具有最大总和的连续子数组，我觉得这很丑：

问题是我内心对这个问题的思考（使用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

Answer 1

在此处查找O(n) Python 解决方案。将其翻译成函数式 Ruby 很简单：

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

Answer 2

我把它写成一个单行字（虽然效率不高，而且非常难以理解）：

(0...arr.length).map{|start| (1..(arr.length-start)).map{|length| arr.slice(start, length).inject(:+)}.max}.max