Pythonで「最小値×サイズ」の積が最大になる部分リストを見つけるプログラム

問題概要

数値のリスト nums と整数 pos が与えられます。このとき、インデックス pos を必ず含むような連続する部分リスト A を選び、「A の最小値 × A の要素数」が最大になるようにした場合の値を返すプログラムを作成します。

例として、入力が nums = [-2, 2, 5, 4]、pos = 3 の場合を考えてみましょう。このとき最適な部分リストは [5, 4] です。最小値は 4、要素数は 2 なので、答えは 4 × 2 = 8 となります。

解法のアプローチ

この問題は貪欲法(グリーディ法)を使うことで効率的に解けます。基本的な考え方は次のとおりです。

• まず、pos の要素のみを含む幅 1 の区間からスタートします。
• その後、区間の左端または右端を 1 つずつ広げていきます。
• どちら側に広げるかを決めるときは、隣接する要素のうち大きい方を選びます。こうすることで、区間の最小値ができるだけ下がらないようにできます。
• 区間を広げるたびに「現在の最小値 × 区間の長さ」を計算し、これまでの最大値を超えていれば答えを更新します。

最終的に区間がリスト全体に達するまで繰り返せば、考えられるすべての「最小値の候補」が網羅されるため、必ず最適解が得られます。

アルゴリズムの手順

1. 答え ans と現在の区間の最小値 m を A[pos] で初期化します。
2. ポインタ i(左端)と j(右端)をともに pos に設定します。
3. 区間のサイズがリスト全体に達するまで、以下を繰り返します。
   • left:左に広げた場合の新しい要素(i - 1 >= 0 なら A[i - 1]、範囲外なら −∞)
   • right:右に広げた場合の新しい要素(j + 1 < len(A) なら A[j + 1]、範囲外なら −∞)
   • left >= right であれば左端を広げ(i -= 1)、m を min(m, A[i]) で更新します。
   • それ以外の場合は右端を広げ(j += 1)、m を min(m, A[j]) で更新します。
   • ans を max(ans, m * (j - i + 1)) で更新します。
4. ans を返します。

Python 実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def solve(self, A, pos):
        NINF = float("-inf")
        ans = m = A[pos]
        i = pos
        j = pos
        for _ in range(len(A) - 1):
            left = A[i - 1] if i - 1 >= 0 else NINF
            right = A[j + 1] if j + 1 < len(A) else NINF
            if left >= right:
                i -= 1
                m = min(m, A[i])
            else:
                j += 1
                m = min(m, A[j])
            ans = max(ans, m * (j - i + 1))
        return ans

ob = Solution()
nums = [-2, 2, 5, 4]
pos = 3
print(ob.solve(nums, pos))

入力

[-2, 2, 5, 4], 3

出力

8

計算量

ループはリストの長さ n に対してちょうど n − 1 回実行され、各ステップの処理は定数時間で済むため、時間計算量は O(n)、必要な追加メモリは O(1) です。すべての部分区間を総当たりする O(n²) の素朴な解法と比べて、大幅に高速に動作します。

まとめ

「最小値 × 長さ」を最大化するタイプの問題では、大きい方の隣接要素へ区間を広げていく貪欲な戦略が非常に有効です。現在の最小値と区間の長さを管理しながら最大値を更新していくだけで、線形時間で最適解を求めることができます。