Pythonでk個の数値を削除した後に隣接する値の最大差を見つけるプログラム

numsという数値のリストがあり、それらが昇順で並べ替えられているとすると、隣接する2つの値の最大差ができるだけ小さくなるように、リストからk値を削除して、最終的に差を見つける必要があります。

したがって、入力がnums =[15、20、30、400、1500] k =2の場合、出力は10になります。これは、[400、1500]を削除して20と30の差を取得する場合と同じです。

これを解決するには、次の手順に従います-

• abs_diff：=nums内の連続するすべての要素の差分のリスト
• 関数dp（）を定義します。これにはi、j、cntが必要です
• cntが0と同じ場合、
  • m：=0
  • iからjの範囲のkについては、
    • m：=最大mおよびabs_diff [k]
  • return m
• dp（i + 1、j、cnt-1）およびdp（i、j-1、cnt-1）の最小値を返します
• メインの方法から次の手順を実行します。
• return dp（0、abs_diffのサイズ-1、k）

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

例

class Solution:
   def solve(self, nums, k):
      abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))]

      def dp(i, j, cnt):
         if cnt == 0:
            m = 0
            for k in range(i, j + 1):
               m = max(m, abs_diff[k])
            return m
         return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1))

      return dp(0, len(abs_diff) - 1, k)
     
ob = Solution()
nums = [15, 20, 30, 400, 1500]
k = 2
print(ob.solve(nums, k))

入力

[15, 20, 30, 400, 1500], 2

出力

10