如何重写在动态规划中使用函数式编程范式在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解决方案，请看here。它翻译成功能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