[Ruby] 最大部分配列問題を解く

最大部分配列問題。
配列内のある部分を足しあわせたとき、その合計が最大化する部分を探す問題。

例えば配列 [-7, 9, -2, 3, 5, -1] があったときに、足しあわせた合計が最大になる部分は、添字1〜4の[9, -2, 3, 5]。要素の合計は15になる。

分割統治法を利用して解くことになる。
Rubyのコードは以下

a = [-7, 9, -2, 3, 5, -1]

MIN_VALUE = -999999.freeze

def crossing_subarray(a, low, high, middle)
  l_sum_max = MIN_VALUE
  l_max = middle
  sum = 0
  middle.downto(low) do |i|
    sum += a[i]
    if sum > l_sum_max
      l_sum_max = sum
      l_max = i
    end
  end

  r_sum_max = MIN_VALUE
  r_max = middle + 1
  sum = 0
  (middle+1).upto(high) do |i|
    sum += a[i]
    if sum > r_sum_max
      r_sum_max = sum
      r_max = i
    end
  end

  return [l_max, r_max, l_sum_max + r_sum_max]
end

def max_subarray(a, low, high)
  return [low, high, a[low]] if low == high

  middle = (low + high) / 2

  l_low, l_high, l_sum = max_subarray(a, low, middle)
  r_low, r_high, r_sum = max_subarray(a, middle + 1, high)
  c_low, c_high, c_sum = crossing_subarray(a, low, high, middle)

  case [l_sum, r_sum, c_sum].max
  when l_sum then [l_low, l_high, l_sum]
  when r_sum then [r_low, r_high, r_sum]
  when c_sum then [c_low, c_high, c_sum]
  end
end

low, high, sum = max_subarray(a, 0, a.size - 1)

puts "a[#{low}] ~ a[#{high}]"
puts "sum => #{sum}"

実行結果

a[1] ~ a[4]
sum => 15

max_subarray

分割統治法を扱っているのはmax_subarrayなので、当然ここで分割がされるわけで。

34行目のmiddleには分割点を入れる。これは配列の中心なのでlowとhighの中央値。

a[low]〜a[high]の最大部分配列は、以下の３択になるので、これらから最大のものを選べば良い。
１．a[low]〜a[middle]の最大部分配列
２．a[middle+1]〜a[high]の最大部分配列
３．a[low]〜a[high]の間でa[middle]をまたがっている最大部分配列

この３番目を求めているのが、crossing_subarray。

crossing_subarray

主に６行目〜１５行目と１７行目〜２５行目の処理に分かれている。
前半では、a[middle]からlowに向かって要素を足しあわせ、最大点を調べる。
後半では、a[middle+1]からhighに向かって要素を足しあわせ、最大点を調べる。
これらを組み合わせたものが、a[low]からa[high]の間でa[middle]をまたがっている最大部分配列になる。