LeetCode 368. Largest Divisible Subset

思路:

想到一个词叫“传递性”,在这边应该也适用。就是如果b%a==0,然后c%b==0,那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了,应该是动态规划的思想,results[i]保存包含数组元素nums[i]的最佳集合,构建集合的时候,首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳(相当于找到c%b==0,当然这里的b是之前results[j]里面的最大元素,即nums[j])然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合,如此继续…

时间复杂度应该是O(n^2)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注