Pythonプログラム：1要素を削除した後、最大値と最小値を同時に含む部分リストの数を求める方法

問題の概要

数値のリスト nums が与えられ、リストから最大1つの要素を削除できるとします。このとき、削除後のリストにおける「最大値と最小値の両方を含む部分リスト（サブリスト）」の数の最大値を求めるのが目的です。

入力例

たとえば、入力が次の場合を考えてみましょう。

nums = [3, 2, 6, 2, 4, 10]

この場合、出力は 8 になります。理由は、要素 10 を削除するとリストは [3, 2, 6, 2, 4] となり、最大値と最小値（この場合は最大値6、最小値2）を両方含む部分リストが以下の8個存在するためです。

• [2, 6]

• [6, 2]

• [2, 6, 2]

• [3, 2, 6]

• [6, 2, 4]

• [2, 6, 2, 4]

• [3, 2, 6, 2]

• [3, 2, 6, 2, 4]

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• まず、リストを受け取って「最大値と最小値を両方含む部分リストの数」を数える関数 check() を定義します。

• check() の内部では、リストの最小値 mn と最大値 mx を求め、それぞれの出現位置を記録する変数 min_pos、max_pos を用意します。

• リストを先頭から順に走査し、各インデックス i の時点で、それまでに見つかった最小値・最大値の位置を使って条件を満たす部分リストの数を累積加算していきます。

• メイン処理では、まず元のリスト全体に対して check() を実行します。

• その後、最小値と最大値がそれぞれ1回しか出現していない場合に限り、その要素を削除したリストでもう一度 check() を実行し、結果の最大値を返します。

アルゴリズムの詳細

check() 関数のロジックは次のとおりです。

• mn := リストの最小値、mx := リストの最大値

• min_pos := None、max_pos := None、ret := 0 で初期化

• 各インデックス i と値 num について繰り返し処理を行います。

  • num が mn と等しければ min_pos := i

  • num が mx と等しければ max_pos := i

  • min_pos または max_pos がまだ None の場合は次の反復へ進む

  • そうでなければ ret += min(min_pos, max_pos) + 1 を計算

• 最後に ret を返します。

メインメソッドでは以下を実行します。

• リストの長さが1以下なら、その長さをそのまま返します。

• ret := check(nums) の結果

• 候補として [リストの最小値, リストの最大値] のそれぞれについて確認します。

  • その値の出現回数が1回だけなら、そのインデックス idx を取得し、その要素を取り除いたリストに対して check() を実行した結果と ret の大きい方を採用します。

• 最終的な ret を返します。

実装例

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

class Solution:
   def solve(self, nums):
      if len(nums) <= 1:
         return len(nums)
      def check(lst):
         mn, mx = min(lst), max(lst)
         min_pos, max_pos = None, None
         ret = 0
         for i, num in enumerate(lst):
            if num == mn:
               min_pos = i
            if num == mx:
               max_pos = i
            if min_pos is None or max_pos is None:
               continue
            ret += min(min_pos, max_pos) + 1
         return ret
      ret = check(nums)
      for rem_cand in [min(nums), max(nums)]:
         if nums.count(rem_cand) == 1:
            idx = nums.index(rem_cand)
            ret = max(ret, check(nums[:idx] + nums[idx + 1 :]))
      return ret
ob = Solution()
nums = [3, 2, 6, 2, 4, 10]
print(ob.solve(nums))

入力

[3, 2, 6, 2, 4, 10]

出力

8

まとめ

このアルゴリズムのポイントは、削除しても意味があるのは最小値か最大値のみという点です。中間の値を削除しても最大値・最小値は変わらないため、結果が改善することはありません。そのため、元のリストに加えて、最小値・最大値が一意である場合にのみそれらを削除したケースを試すだけで十分であり、効率的に答えを求められます。時間計算量は O(n) ベースで、追加の削除チェックも定数回しか行わないため、大きなリストに対しても高速に動作します。