leetcode Largest Divisible Subset

leetcode Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj% Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Example 2:

题目地址:leetcode Largest Divisible Subset

题意:给定一个数组,求其中的一个最大子集,要求该子集中任意的两个元素满足 x % y ==0 或者 y % x==0

思路:其实和求最大上升子序列LIS差不多,只不过这题要求输出序列而已。

先把数组排好序。首先要明确,若a<b且b%a==0 ,  b <c 且 c%b==0那么必然有c%a==0

我们设dp[i] 为最大的子集长度,更新的时候保存上一个的下标即可。

C++

Java

Python

 

 

本题是leetcode 368 Largest Divisible Subset 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Largest Divisible Subset
本文地址:https://www.hrwhisper.me/leetcode-largest-divisible-subset/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

10 thoughts on “leetcode Largest Divisible Subset

  1. hrwhisper, 谢谢你的讲解,很有帮助,但是我发现最后一行是不是该加一个 Collections.sort(ans) 呀,要不你给的答案是in reverse order。

  2. //for (int j = 0; j = 0; j–) {
    if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
    dp[i] = dp[j] + 1;
    index[i] = j;
    break;
    }
    }
    内循环,如果从后向前,这样算dp[i]好像更快一点

Leave a Reply

Your email address will not be published. Required fields are marked *