Pythonで指定した長さの最大部分配列を見つける方法を解説

さまざまな整数値を含む配列と、指定された長さ k が与えられたとします。このとき、配列の中から指定された長さをもつ「最大の部分配列（サブ配列）」を見つける必要があります。

ここで「ある部分配列が別の部分配列より大きい」とは、両者を左から順に要素ごとに比較していき、初めて異なる要素が現れた位置 i において subarray1[i] ≠ subarray2[i] かつ subarray1[i] > subarray2[i] が成り立つことを意味します。いわゆる辞書式順序による比較の考え方です。

たとえば、入力が nums = [5, 3, 7, 9]、k = 2 の場合、出力は [7, 9] となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• start を「配列のサイズ − k」で初期化する（末尾側のウィンドウ開始位置）
• max_element を nums[start] に、max_index を start に設定する
• start が 0 以上である間、次の処理を繰り返す
  • nums[start] > max_element であれば、max_element を nums[start] に、max_index を start に更新する
  • start を 1 減らす
• ループ終了後、nums[max_index : max_index + k] を返す

この手法では、長さ k のウィンドウの開始位置となり得るインデックスだけを右端から左へ向かって走査し、先頭要素が最大となる位置を記録していきます。配列の長さを n とすると、計算量は約 O(n) と非常に効率的です。

実装例

理解を深めるために、実際の Python コードを見てみましょう。

def solve(nums, k):
    start = len(nums) - k
    max_element = nums[start]
    max_index = start

    while start >= 0:
        if nums[start] > max_element:
            max_element = nums[start]
            max_index = start

        start -= 1

    return nums[max_index:max_index + k]

print(solve([5, 3, 7, 9], 2))

入力

[5, 3, 7, 9], 2

出力

[7, 9]

動作の流れ

入力 nums = [5, 3, 7, 9]、k = 2 の場合、処理は次のように進みます。

• 初期状態：start = 2、max_element = 7、max_index = 2
• start = 1：nums[1] = 3 は 7 より小さいため更新なし
• start = 0：nums[0] = 5 は 7 より小さいため更新なし
• 結果として nums[2:4] ＝ [7, 9] が返される

注意点

このアルゴリズムは「ウィンドウの先頭要素の最大値」に着目して開始位置を決定します。先頭要素が同じ値になる複数のウィンドウが存在する場合は、後続の要素も含めて辞書式順序で比較しないと正しい答えが得られないことがあります。そのようなケースにも対応したい場合は、候補となるウィンドウ全体を比較する処理を追加しておくとより安全です。