Pythonで1つの要素のみを削除した後、最大値と最小値を含むサブリストの数を見つけるプログラム

numsという番号のリストがあり、リスト内の最大1つの要素を削除できるとします。結果のリストの最大値と最小値の両方を含むサブリストの最大数を見つける必要があります。

したがって、入力がnums =[3、2、6、2、4、10]のような場合、出力は8になります。10を削除すると、[3、2、6、2、4]が得られます。最大値と最小値の両方を含む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（）を定義します。これには時間がかかります

• mn：=lstの最小値、mx：=lstの最大値

• min_pos：=null、max_pos：=null

• ret：=0

• lstの各インデックスiと値numについて、実行します

  • numがmnと同じ場合、

    • min_pos：=i

  • numがmxと同じ場合、

    • max_pos：=i

  • min_posがnullまたはmax_posがnullの場合、

    • 次のイテレーションに行く

  • ret：=ret + min_posの最小値と（max_pos + 1）

• retを返す

• メインの方法から、次のようにします-

• numsのサイズが<=1の場合、

  • numsのサイズを返す

• ret：=check（nums）

• [最小nums、最大nums]の各rem_candに対して、実行

  • rem_candの出現が1の場合、

    • idx：=rem_candの数値単位のインデックス

    • ret：=retの最大値とcheck（nums[インデックス0からidx-1まで]はnums[インデックスidx+1から終了まで]を連結します

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

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