哪本书，哪一段没有看懂。。

def f a
  return 0 if a.empty?
  [
    a.inject(:+), # sum
    f(a[0...-1]), # 除去最后一个
    f(a[1..-1])   # 除去第一个
  ].max
end

f [-2,11,-4,13,-5,-2]

edit: #2 楼 #3 楼 是 O(n) 的比上面这个要快得多

#1 楼 @luikore 有个 O(n) 的算法的

(a.inject [0, 0] do |(a, b), c|
  a += c
  a = 0 if a < 0
  b = a if a > b
  [a, b]
end)[1]

def max_subarray(a)
  max_ending_here = 0
  max_so_far = 0

  a.each do |x|
    max_ending_here = [0, x, max_ending_here + x].max
    max_so_far = [max_so_far, max_ending_here].max
  end

  max_so_far
end

puts max_subarray([-2, 11, -4, 13, -5, -2])

我能吐槽一下楼上的 variable name 么 xD 不过确实很简缩

关于 LZ 说的分治算法我觉得照着算法画个树状图出来 看看每个阶段是怎样分解又怎样合并的 应该就好懂了 (后者换个简单一点的题 我觉得分治之类的懂一题就都懂了)

#1 楼 @luikore 这样分治复杂度好高，不如二分，用类似线段树的做法～～O(nlogn) 实际上只需要一个 O(n) 的贪心就好了，如 2,3 楼的算法

#4 楼 @lostleaf 嗯.. 是的 O(n) 贪心就够了

#3 楼 @leozwa 嗯，接受吐槽>_<#