Maximum Subarray
整数のリスト nums が与えられます。部分配列とは、間隔を空けずに隣り合う要素を取り出したもので、少なくとも1つの要素を含む必要があります。nums の部分配列が取り得る最大の合計を返してください。返すのは合計のみで、部分配列自体ではありません。
関数
- numsinteger-array
- 少なくとも1つの要素を含む整数のリスト
- 戻り値integer
- 空でない隣接要素の連続区間の最大合計
制約
1 ≤ nums.length ≤ 105-104 ≤ nums[i] ≤ 104- 答えは常に32ビット符号付き整数に収まります。
例
- 入力
- nums = [2, -4, 3, -1, 5, -6, 1]
- 出力
- 7
- 説明
- 一連の値
[3, -1, 5]の合計は7です。左に伸ばすと-4、続いて2が加わり、差し引きで2の減少になります。右に伸ばすと-6、続いて1が加わり、差し引きで5の減少になります。他の一連の値がこれを上回ることはありません。
- 入力
- nums = [-3, -1, -2]
- 出力
- -1
- 説明
- すべての数値が負なので、連続する部分が長くなるほど合計は小さくなり、最良の部分は単一の要素 -1 です。部分配列を空にすることはできないため、答えは 0 ではなく -1 です。
発展問題
また、リストを半分に分割し、中央をまたぐ連続部分を処理することで、分割統治法を使って O(n log n) で解くこともできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ちょうどある位置で終わる連続区間に注目しましょう。ここで終わる最良の連続区間は、その直前の位置で終わる最良の連続区間とどのように関係しているでしょうか？
現在の要素で終わる連続区間は、その直前で終わった連続区間を続けるか、この要素から新たに始めます。続けることが有効なのは、直前の連続区間の合計が正の場合だけです。
リストを一度走査し、2つの数値を保持します。現在の要素で終わる連続部分の最大の合計と、これまでに見つかった最大の合計です。両方を最初の要素に設定するため、負の数だけのリストでも最大の要素が返されます。
解説
n 個の数値からなるリストには、およそ n²/2 個の部分配列があるため、要素数が 10^5 の場合、それらを一つずつ確認するのは多すぎます。難しいのは負の数です。後続の要素でその分を補えるなら、連続部分列に負の要素を残し、補えないなら、その要素より前のすべてを切り捨てる必要があります。Kadane のアルゴリズムは、各要素で一度比較するだけでその判断を行います。
すべての部分配列を合計する
正しいが、最大のテストでは終わらない
考え方
すべての部分配列には最初のインデックス left と最後のインデックス right があるため、すべての組み合わせを試せば最適なものが見つかります。left を固定して right を前に進めながら、新しい要素を累積する total に加えていきます。各部分配列につき加算は1回で済み、3重ループは必要ありません。
それでも約 n²/2 個の組み合わせが残り、要素が10^5個の場合、加算は50億回になります。
アルゴリズム
bestを最初の要素に設定します。- 各開始インデックス
leftについて、累積値totalを0に設定します。 rightをleftからリストの末尾まで移動させ、nums[right]をtotalに加算します。- 加算するたびに、
totalの方が大きければ、totalをbestに保存します。 bestを返します。
def maxSubArray(nums):
best = nums[0]
for left in range(len(nums)):
total = 0
# Grow the subarray that starts at left by one element at a time
for right in range(left, len(nums)):
total += nums[right]
best = max(best, total)
return bestカデーンのアルゴリズム
考え方
インデックス i で終わる最良の連続部分列は、nums[i] 単独か、i-1 で終わる最良の連続部分列に nums[i] を加えたものです。これは、i-1 で終わる他の連続部分列に、より大きな合計値を持つものがないためです。そこで、現在の要素で終わる連続部分列の最良の合計値を表す endingHere という数値を1つ保持します。次の要素 x では、その値は x と endingHere + x の大きい方になります。連続部分列の合計が正である間はそのまま伸ばし、0以下になったら x から始め直します。
最良の部分配列はどこかで終わるため、答えは endingHere が取る最大値です。最初の例では、その値は 2, -2, 3, 2, 7, 1, 2 と変化し、答えは 7 です。
アルゴリズム
endingHereとbestを最初の要素に設定します。- 後続の各要素
xについて、endingHereをxとendingHere + xの大きい方に設定します。 bestをbestとendingHereの大きい方に設定します。- 最後の要素の後に、
bestを返します。
def maxSubArray(nums):
current = nums[0]
best = nums[0]
for i in range(1, len(nums)):
current = max(nums[i], current + nums[i])
best = max(best, current)
return best
落とし穴と境界ケース
bestを 0 から始める。[-3, -1, -2]の場合、-1 ではなく 0 が返される。最初の要素から始める。- 累積和を
max(0, endingHere + x)で 0 以上にする。同じリストで失敗する。代わりにxと比較する。 - 正の数だけを合計する。要素は隣り合っていなければならないため、最初の例の答えは 2 + 3 + 5 + 1 = 11 ではなく 7 になる。
endingHereとbestをnums[0]に設定せずに、インデックス 1 からループを始める。[-5]のような 1 要素のリストでは、-5 が返されなければならない。
よくある質問3
カダネのアルゴリズムとは何ですか？
Kadaneのアルゴリズムは、1回の走査で連続する部分配列の最大和を求めます。現在の要素で終わる部分列の最大和を保持し、新しい要素ごとに、その部分列を延長するか、新たに開始するかを選びます。これらの和の最大値が答えです。
Maximum Subarray の時間計算量は何ですか？
Kadaneのアルゴリズムは、各要素を1回ずつ確認するため、O(n)時間、O(1)の追加領域で実行できます。累積合計を使ってすべての部分配列を確認するとO(n²)かかり、各部分配列の合計を最初から計算するとO(n³)かかります。
なぜ最大部分配列問題は動的計画法の問題なのでしょうか？
インデックス i で終わる連続部分列の最大の合計は、i-1 で終わる連続部分列の最大の合計だけに依存します。これはインデックスに関する漸化式であり、動的計画法の典型的な形です。Kadane のアルゴリズムは表全体ではなく最新の値だけを保持するため、必要な領域は O(1) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def maxSubArray(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
nums = [2, -4, 3, -1, 5, -6, 1]
期待される出力
7