Maximum Sum Subarray of Size K
整数の配列 nums とウィンドウの長さ k が与えられます。隣接する要素がちょうど k 個連続するすべての区間を調べ、その中で最大の合計を返してください。値は負になることもあるため、答えも負になる場合があります。
関数
- numsinteger-array
- 整数の配列
- kinteger
- 各ウィンドウが保持する隣接要素の数
- 戻り値integer
- 連続する任意の k 個の要素の合計の最大値
制約
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104
例
- 入力
- nums = [4, -1, 3, 7, -2, 5, 1]k = 3
- 出力
- 10
- 説明
- 長さ3の5つのウィンドウの合計は、
6、9、8、10、4です。最大値は7 + (-2) + 5 = 10です。
- 入力
- nums = [-3, -8, -1, -6]k = 2
- 出力
- -7
- 説明
- すべての値が負なので、各ウィンドウの合計も負です。
-11、-9、-7です。その中で最大なのは-1 + (-6) = -7です。
- 入力
- nums = [5, -2, 4]k = 3
- 出力
- 7
- 説明
kが配列の長さと等しい場合、ウィンドウは1つで、配列全体がそのウィンドウとなり、5 + (-2) + 4 = 7です。
提出時に隠しテスト+15件
発展問題
最適なウィンドウの開始位置も返せますか？複数のウィンドウが同率の場合は、最も左側のものを選んでください。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
隣り合う2つのウィンドウの合計を書き出してみましょう。たとえば、インデックス0から始まるものと、インデックス1から始まるものです。これらに共通するものは何でしょうか？
k-1個の要素を共有しています。ウィンドウを右に1つ移動すると、新しい要素が1つ追加され、古い要素が1つ削除されるため、新しい合計は2つの操作で古い合計から求められます。最初の
k個の要素を一度合計します。その後、kから末尾までの各iについて、nums[i]を加え、nums[i-k]を引き、これまでに得た最大の合計を保持します。
解説
n-k+1 個のウィンドウがあり、それぞれを最初から合計すると k 回の加算が必要です。ポイントは、隣り合う2つのウィンドウが、2つの要素を除いてすべて重なり合っていることです。ウィンドウを作り直すのではなく、スライドさせます。1つの値が入り、1つの値が出るため、各ウィンドウの合計は2回の操作で求められます。
すべてのウィンドウを合計する
正しいが、最大のテストでは終わらない
考え方
ウィンドウは、開始位置によって決まります。インデックス 0、1、さらに n-k までの位置から開始できます。それより後から開始すると、配列の末尾を越えてしまうためです。各開始位置について、k 個の要素を合計し、その合計をこれまでの最大値と比較します。
[4, -1, 3, 7, -2, 5, 1] と k = 3 の場合、合計は 6, 9, 8, 10, 4 となり、答えは 10 です。最大値は最初のウィンドウの合計、または最小の整数で初期化し、決して 0 にしてはいけません。すべての値が負の場合、0 は実際のどのウィンドウの合計よりも大きくなるためです。
計算量は (n-k+1) × k 回の加算です。k が n の約半分のときに最大となります。n = 10^4、k = 5000 の場合、加算回数は 5001 × 5000、つまり約 2.5 × 10^7 回となり、そのほとんどは直前のウィンドウですでに行った計算の繰り返しです。
アルゴリズム
bestに可能な限り小さい値を設定します。0からn-kまでの各開始位置について、total = 0を設定します。nums[start]からnums[start+k-1]までをtotalに加算します。totalがbestを上回ったら、その値を保存します。bestを返します。
def maxSumSubarray(nums, k):
n = len(nums)
best = None
for start in range(n - k + 1):
total = 0
for i in range(start, start + k):
total += nums[i]
if best is None or total > best:
best = total
return best固定ウィンドウをスライドする
考え方
インデックス0から始まるウィンドウと、インデックス1から始まるウィンドウを比較します。k = 3のとき、[4, -1, 3, 7, -2, 5, 1]では、それぞれ4 + (-1) + 3 = 6と(-1) + 3 + 7 = 9です。どちらにも-1と3が含まれています。2つ目の合計は、1つ目の合計に、入ってきた値7を足し、出ていった値4を引いたものです。6 + 7 - 4 = 9となります。
これは、どのステップでも成り立ちます。ウィンドウの右端がインデックスiに移動すると、インデックスiの要素が入り、インデックスi-kの要素が出ていきます。つまり、最初のウィンドウの合計を一度だけ計算し、その後は各ステップで1回の加算と1回の減算によって合計を更新します。合計は6, 9, 8, 10, 4となり、総当たり法と同じ結果が得られます。その中の最大値を保持します。
各要素は一度入ってきて、最大でも一度出ていくため、時間計算量はO(n)です。保持するのは現在のウィンドウの合計と最大値の2つなので、追加の空間計算量はO(1)です。ここでの合計はどれも10^4 × 10^4 = 10^8を超えないため、32ビット整数で十分です。
アルゴリズム
nums[0]からnums[k-1]までを合計してwindowに格納します。best = windowを設定します。kからn-1までの各iについて、nums[i]を加算し、nums[i-k]を減算します。- 各ステップの後、
bestとwindowの大きい方をbestに設定します。 bestを返します。
def maxSumSubarray(nums, k):
# Sum of the first window, nums[0..k-1].
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
# Slide one step right: nums[i] enters, nums[i-k] leaves.
window += nums[i] - nums[i - k]
best = max(best, window)
return best
落とし穴と境界ケース
ウィンドウの考え方は単純ですが、バグは開始値とインデックスに潜んでいます。
bestを0で開始する。[-3, -8, -1, -6]とk = 2の場合、実際の答えは-7ですが、bestが0だとそれを上回る値はなく、答えとして返されてしまいます。- 間違った要素を引く。
nums[i]が入るとき、出ていくのはnums[i-k]です。nums[i-k+1]やnums[i-k-1]を使うと、ウィンドウの長さが間違ってしまいます。 - 全探索を開始位置1つ分早く終了する。最後のウィンドウは
n-kから始まるため、ループではそこも含める必要があります。k = nの場合、それが唯一のウィンドウです。オフバイワンの間違いがあるとウィンドウを1つも調べず、bestの開始値を返してしまいます。 - ループの後でしか比較しない。最初のウィンドウが最大になることもあるため、最初の合計も比較するか、それを使って
bestを初期化してください。 - RとLuaでは1から数え始めることを忘れる。最初のウィンドウは
nums[1..k]で、nums[i]が入るときに出ていく要素はやはりnums[i-k]です。
よくある質問4
固定サイズのスライディングウィンドウとは何ですか？
配列上を一度に1ステップずつ移動する、隣り合った要素ちょうどk個の範囲です。各位置で範囲を最初から再計算する代わりに、累積値を更新します。右側から入る要素を加え、左側から出る要素を取り除きます。これにより、処理量はO(n·k)からO(n)になります。
サイズ k の部分配列の最大和を求める時間計算量はどれくらいですか？
スライディングウィンドウを使うと、時間計算量はO(n)、追加領域はO(1)です。最初のウィンドウの合計を求めるために1回走査し、その後は各ステップで1回の加算と1回の減算を行います。各ウィンドウの合計を個別に求めると、(n-k+1) × k回の加算が必要になり、これはO(n·k)です。n = 10^4、k = 5000の場合、約2.5 × 10^7となります。
これは最大部分配列問題とどう違うのですか？
ここでは長さが k に固定されているため、すべての候補がウィンドウとなり、スライディングサムですべてを網羅できます。最大部分配列問題では長さは自由であり、各要素で現在の連続部分を延長するか、新しく始めるかを判断するKadaneのアルゴリズムが必要です。固定ウィンドウにはその選択肢がありません。
累積和でも解けるでしょうか？
はい。最初の i 個の要素の合計として prefix[i] を作ると、s から始まるウィンドウの合計は prefix[s+k] - prefix[s] になります。これも時間計算量は O(n) ですが、合計値を n+1 個保存します。スライディングウィンドウなら、2つの変数で同じ合計を求められます。
Python
def maxSumSubarray(nums, k):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [4, -1, 3, 7, -2, 5, 1] k = 3
期待値
10