読者です 読者をやめる 読者になる 読者になる

最大部分配列

分割統治の例です。配列の中から、部分和が最大となる部分配列を探し出し、その最初と最後のインデックス、および最大の部分和を返します。
重要なのはメソッド 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]