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

我编写了以下代码来查找具有最大和的相邻子数组，我对此做了一些修改：
问题是我对这个问题的内在思考（使用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

最佳答案

寻找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

关于ruby - 如何使用ruby中的函数式编程范例重写在动态编程中查找最大连续子数组？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11870489/