Pythonで「良い部分配列」の最大スコアを求めるアルゴリズムと実装

問題の概要

整数配列 nums とインデックス k が与えられます。部分配列 (i, j) のスコアは、次のように定義されます。

score(i, j) = min(nums[i..j]) × (j − i + 1)

つまり「部分配列内の最小値 × 部分配列の長さ」です。ここで、i ≤ k ≤ j を満たす部分配列を「良い部分配列(good subarray)」と呼びます。この記事の目的は、良い部分配列の中から最大のスコアを見つけることです。

入力例

nums = [2,5,4,8,5,6]、k = 3 の場合を考えてみましょう。最適な部分配列は (1, 5) で、nums[1..5] の最小値は 4 です。したがって、スコアは 4 × (5 − 1 + 1) = 20 となります。

解法の考え方

この問題は、インデックス k を中心に領域を左右へ拡張していく貪欲法を使えば、O(n) の計算量で効率的に解けます。基本的なアイデアは次のとおりです。

• まず k の位置だけを範囲とし、そこから左右のポインタ i と j を広げていきます。
• 現在の最小値 minNum 以上の要素は、スコアを下げることなく範囲に取り込めます。そこで、minNum 未満の要素に行き当たるまでポインタを進めます。
• 各段階で「現在の幅 × 現在の最小値」を計算し、答えを更新します。
• その後、両端のうち大きい方の値を新しい最小値の候補として採用し、再度拡張を行います。これにより、あり得るすべての「最小値の水準」を漏れなく評価できます。

アルゴリズムの手順

1. ans と minNum を nums[k] で初期化する。
2. ポインタ i と j をどちらも k に設定する。
3. i > -1 または j < 配列のサイズ である間、次を繰り返す。
   • nums[i] ≥ minNum である限り、i を左へ移動する。
   • nums[j] ≥ minNum である限り、j を右へ移動する。
   • ans を max(ans, (j − i − 1) × minNum) で更新する。
   • minNum を、範囲外の場合は -1 として、nums[i] と nums[j] の大きい方で更新する。
4. ans を返す。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(nums, k):
    ans = nums[k]
    minNum = nums[k]
    i = k
    j = k
    while i > -1 or j < len(nums):
        while i > -1 and nums[i] >= minNum:
            i -= 1
        while j < len(nums) and nums[j] >= minNum:
            j += 1
        ans = max(ans, (j - i - 1) * minNum)
        minNum = max(nums[i] if i > -1 else -1,
                     nums[j] if j < len(nums) else -1)
    return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))

実行結果

入力:

[2,5,4,8,5,6], 3

出力:

20

計算量

• 時間計算量: O(n)。左右のポインタはそれぞれ配列を一度だけ走査するため、全体で線形時間で処理できます。
• 空間計算量: O(1)。追加のデータ構造は一切不要です。

まとめ

「最小値 × 長さ」で定義されるスコアの最大化問題は、単調な拡張戦略(貪欲法)によって効率的に解けます。k を必ず含むという制約があるため、k を起点に左右へ領域を広げるこの手法が自然な選択になります。同様のパターンは LeetCode の「Maximum Score of a Good Subarray」などの問題にも応用できるので、ぜひマスターしておきましょう。