アルゴリズム：最大部分配列和（最大部分区間和）問題

問題定義#

与えられた正数と負数を含む 1 次元配列 $A[1..n]$ から、連続した部分配列 $A[i..j]$ を探し、その部分配列の要素の和が最大になるようにします。すなわち、次を求めます：

$\max _{1\leq i\leq j\leq n} \sum_{k=i}^j A[k]$

そして、この最大値を返します。場合によっては、この部分配列の開始位置 $i, j$ も返す必要があります。

アプリケーションシーン#

株式売買分析：利益を最大化するための買い時と売り時を探します（すなわち、最も上昇幅の大きい期間）。

財務データ分析：企業の利益が最も良い期間を探します。

画像処理：ピクセル配列の中で明るさが最も集中している領域を見つけます。

DNA 配列分析：遺伝子スコア配列の中で最適なセグメントを探します。

ブルートフォース法による解法（列挙）#

max_sum = float('-inf')
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += A[j]
        if sum > max_sum:
            max_sum = sum

$O(n^2)$ 個の部分配列があります。時間計算量は $O(n^2)$ です。部分配列の和は累積中に直接 $O(1)$ で求められます。

分治法による解法#

考え方：配列を左右 2 つの部分に分け、左半分と右半分の最大部分配列を再帰的に解決し、次に中央を横断する最大部分配列を処理します。以下の 3 つのケースをそれぞれ考慮します：
最大部分配列が左側にある
最大部分配列が右側にある
最大部分配列が中点を横断する

時間計算量
再帰式： $T(n) = 2T(n/2) + O(n)$ 、その後主定理を使用して求めるか、直接分析して $O(n\log n)$ を得ます。

def max_subarray(A, left, right):
    if left == right:
        return A[left], left, right

    mid = (left + right) // 2

    left_sum, l_start, l_end = max_subarray(A, left, mid)
    right_sum, r_start, r_end = max_subarray(A, mid + 1, right)
    cross_sum, c_start, c_end = max_crossing_subarray(A, left, mid, right)

    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_sum, l_start, l_end
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_sum, r_start, r_end
    else:
        return cross_sum, c_start, c_end


def max_crossing_subarray(A, left, mid, right):
    sum = 0
    left_max = float('-inf')
    max_left = mid
    for i in range(mid, left - 1, -1):
        sum += A[i]
        if sum > left_max:
            left_max = sum
            max_left = i

    sum = 0
    right_max = float('-inf')
    max_right = mid + 1
    for j in range(mid + 1, right + 1):
        sum += A[j]
        if sum > right_max:
            right_max = sum
            max_right = j

    return left_max + right_max, max_left, max_right

動的計画法#

考え方：変数 current_sum を使用して、現在の位置で終了する最大部分配列の和を表します。現在の要素が単独でより優れている場合は部分配列を再起動し、そうでなければ現在の部分配列を拡張します。

反復方程式： $dp[i] = \max\{ dp[i-1] + A[i], A[i]\}$

時間計算量： $O(n)$

current_sum = max_sum = A[0]
for i in range(1, n):
    current_sum = max(A[i], current_sum + A[i])
    max_sum = max(max_sum, current_sum)

練習問題#

洛谷 P1115 最大部分列和