Pythonですべてのペアの1つの要素が他の要素で割り切れる最大のサブセットの長さを見つけるプログラム

numsと呼ばれる一意の番号のリストがあるとすると、（i、j）のようなサブセット内の要素のすべてのペアがi％j =0またはj％i =0のいずれかを満たすように、最大​​のサブセットを見つける必要があります。このサブセットのサイズを見つける必要があります。

したがって、入力がnums =[3、6、12、24、26、39]の場合、有効な最大のサブセットは[3、6、12、24]であるため、出力は4になります。

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

• dp：=サイズ番号のリストと1で埋める
• リスト番号を並べ替える
• n：=numsのサイズ
• n <=1の場合、
  • return n
• ans：=0
• 1からnの範囲のiについては、
  • 0からiの範囲のjについては、
    • nums[i]がnums[j]で割り切れる場合、
      • dp [i]：=最大dp[i]およびdp[j] + 1
  • ans：=ansとdp[i]の最大値
• 回答を返す

例（Python）

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

class Solution:
   def solve(self, nums):
      dp = [1] * len(nums)
      nums.sort()
      n = len(nums)
      if n <= 1:
         return n
      ans = 0
      for i in range(1, n):
         for j in range(0, i):
            if nums[i] % nums[j] == 0:
            dp[i] = max(dp[i], dp[j] + 1)
         ans = max(ans, dp[i])
      return ans
ob = Solution()
nums = [3, 6, 12, 24, 26, 39]
print(ob.solve(nums))

入力

[3, 6, 12, 24, 26, 39]

出力

4