Leetcode 368. Largest Divisible Subset

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Largest Divisible Subset

2. Solution

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def largestDivisibleSubset(self, nums):
nums.sort()
length = len(nums)
dp = [1] * length
for i in range(length):
for j in range(i + 1, length):
if nums[j] % nums[i] == 0:
dp[j] = max(dp[j], dp[i] + 1)
max_index = dp.index(max(dp))
result = [nums[max_index]]
for i in range(max_index - 1, -1 , -1):
if nums[max_index] % nums[i] == 0 and dp[i] == dp[max_index] - len(result) and result[-1] % nums[i] == 0:
result.append(nums[i])
result.reverse()
return result

Reference

  1. https://leetcode.com/problems/largest-divisible-subset/
如果有收获,可以请我喝杯咖啡!