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

Question

我编写了以下代码来查找具有最大总和的连续子数组，我认为这非常难看:

问题是我内心对于这个问题的思考(使用DP)是势在必行的。我怎样才能重构这段代码并使其更加实用(并且干燥)？关于如何用函数式语言思考算法有什么建议吗？ (不过也许应该是一个单独的问题)。

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

看here对于 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