最大部分配列問題。
配列内のある部分を足しあわせたとき、その合計が最大化する部分を探す問題。
例えば配列 [-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]の最大部分配列は、以下の3択になるので、これらから最大のものを選べば良い。
1.a[low]〜a[middle]の最大部分配列
2.a[middle+1]〜a[high]の最大部分配列
3.a[low]〜a[high]の間でa[middle]をまたがっている最大部分配列
この3番目を求めているのが、crossing_subarray。
crossing_subarray
主に6行目〜15行目と17行目〜25行目の処理に分かれている。
前半では、a[middle]からlowに向かって要素を足しあわせ、最大点を調べる。
後半では、a[middle+1]からhighに向かって要素を足しあわせ、最大点を調べる。
これらを組み合わせたものが、a[low]からa[high]の間でa[middle]をまたがっている最大部分配列になる。