分割統治アルゴリズムで最大部分配列和を攻略する
「n 個の整数からなる配列のうち、最大部分配列の和を求める」方法はいくつもありますが、そのうちの一つが分割統治（Divide & Conquer）アルゴリズムを利用する方法です。やり方としては、配列を再帰的に 2 つに分割し、分割したそれぞれの左側と右側における最大部分配列和、および左右両方にまたがる部分の最大和を求め、これらを組み合わせることで現在の配列における解を求めます。
以下の擬似コードは、分割統治アルゴリズムによって最大部分配列和を計算するイメージです:
def max_subarray(a):
# ベースケース（基本条件）
if len(a) == 0:
return float('-inf'), float('-inf'), float('-inf')
if len(a) == 1:
return a[0], a[0], a[0]
# 分割（左側と右側パートの答えを取得）
ll, lmax, lr = max_subarray(a[:len(a) // 2])
rl, rmax, rr = max_subarray(a[len(a) // 2:])
lsum = sum(a[:len(a) // 2])
rsum = sum(a[len(a) // 2:])
# 3つの値を取得し、最大プレフィックス、最大サフィックス、および合計最大和を返す
return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)この問題では、上記の
max_subarray 関数の中で呼び出されている conquer パートを実装する必要があります。具体的には、8 つの値が与えられたとき、それをもとに「最良のプレフィックス和」「ミッドポイントをまたぐ最大部分配列和」「最良のサフィックス和」の 3 つを正しく計算する部分です。与えられる 8 つの値は以下のものです:- 左部分配列における最良のプレフィックス和
- 左部分配列の最大部分配列和
- 左部分配列における最良のサフィックス和
- 左部分配列全体の要素の和
- 右部分配列における最良のプレフィックス和
- 右部分配列の最大部分配列和
- 右部分配列における最良のサフィックス和
- 右部分配列全体の要素の和
入力
入力の唯一の行には、上記の順番で 8 つの整数が含まれています。これらの整数の絶対値は を超えません。
出力
プログラムは 3 つの値、つまり「最良のプレフィックス和」「ミッドポイントをまたぐ最大和」「最良のサフィックス和」を出力しなければなりません。
例
入力 | 出力 |
7 13 9 6 7 9 3 -2 | 13 16 7 |
7 13 9 6 5 25 3 1 | 11 25 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB