Python에서 모든 쌍의 한 요소가 다른 요소로 나눌 수 있는 가장 큰 부분 집합의 길이를 찾는 프로그램

<시간/>

nums라는 고유 숫자 목록이 있다고 가정하고 (i, j)와 같은 부분 집합의 모든 요소 쌍이 i % j =0 또는 j % i =0을 충족하는 가장 큰 부분 집합을 찾아야 합니다. 그래서 우리는 이 하위 집합의 크기를 찾아야 합니다.

따라서 입력이 nums =[3, 6, 12, 24, 26, 39]와 같으면 가장 큰 유효한 부분 집합이 [3, 6, 12, 24]이므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dp :=크기 숫자 목록 및 1로 채우기
목록 번호 정렬
n :=숫자 크기
n <=1이면
- 반환 n
ans :=0
1~n 범위의 i에 대해
- 0~i 범위의 j에 대해
  - nums[i]가 nums[j]로 나누어지면
    - dp[i] :=dp[i] 및 dp[j] + 1의 최대값
- ans :=ans 및 dp[i]의 최대값
반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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]