最大部分配列
分割統治の例です。配列の中から、部分和が最大となる部分配列を探し出し、その最初と最後のインデックス、および最大の部分和を返します。
重要なのはメソッド fmcs(find-max-crossing-subarray)です。
class Array def fmcs(low, mid, high) left_sum = - Float::INFINITY max_left = max_right = nil sum = 0 mid.downto(low) do |i| sum += self[i] next unless sum > left_sum left_sum = sum max_left = i end right_sum = - Float::INFINITY sum = 0 (mid + 1).upto(high) do |j| sum += self[j] next unless sum > right_sum right_sum = sum max_right = j end return max_left, max_right, left_sum + right_sum end def fms(low, high) return low, high, self[low] if high == low mid = (low + high) / 2 left_low, left_high, left_sum = fms(low, mid) right_low, right_high, right_sum = fms(mid + 1, high) cross_low, cross_high, cross_sum = fmcs(low, mid, high) if left_sum >= right_sum and left_sum >= cross_sum return left_low, left_high, left_sum elsif right_sum >= left_sum and right_sum >= cross_sum return right_low, right_high, right_sum else return cross_low, cross_high, cross_sum end end def find_maximum_subarray fms(0, self.size - 1) end end a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7] p a.find_maximum_subarray #=>[7, 10, 43]
『アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)』p.59-60
全数探索ではこんな風でしょうか。
class Array def quarry_all_subarray_index size.times do |i| i.upto(size - 1) {|j| yield(i, j)} end end def find_maximum_subarray max = - Float::INFINITY mi = mj = nil quarry_all_subarray_index do |i, j| sum = self[i..j].inject(:+) mi, mj, max = i, j, sum if max < sum end return mi, mj, max end end a = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7] p a.find_maximum_subarray #=>[7, 10, 43]