Array
Math
Dynamic Programming
Sorting
Description
Given a set of distinct positive integers nums
, return the largest subset answer
such that every pair (answer[i], answer[j])
of elements in this subset satisfies:
answer[i] % answer[j] == 0
, or
answer[j] % answer[i] == 0
If there are multiple solutions, return any of them.
Example 1:
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
Example 2:
Input: nums = [1,2,4,8]
Output: [1,2,4,8]
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 109
All the integers in nums
are unique .
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution :
def largestDivisibleSubset ( self , nums : List [ int ]) -> List [ int ]:
nums . sort ()
n = len ( nums )
f = [ 1 ] * n
k = 0
for i in range ( n ):
for j in range ( i ):
if nums [ i ] % nums [ j ] == 0 :
f [ i ] = max ( f [ i ], f [ j ] + 1 )
if f [ k ] < f [ i ]:
k = i
m = f [ k ]
i = k
ans = []
while m :
if nums [ k ] % nums [ i ] == 0 and f [ i ] == m :
ans . append ( nums [ i ])
k , m = i , m - 1
i -= 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
public List < Integer > largestDivisibleSubset ( int [] nums ) {
Arrays . sort ( nums );
int n = nums . length ;
int [] f = new int [ n ] ;
Arrays . fill ( f , 1 );
int k = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
if ( nums [ i ] % nums [ j ] == 0 ) {
f [ i ] = Math . max ( f [ i ] , f [ j ] + 1 );
}
}
if ( f [ k ] < f [ i ] ) {
k = i ;
}
}
int m = f [ k ] ;
List < Integer > ans = new ArrayList <> ();
for ( int i = k ; m > 0 ; -- i ) {
if ( nums [ k ] % nums [ i ] == 0 && f [ i ] == m ) {
ans . add ( nums [ i ] );
k = i ;
-- m ;
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public :
vector < int > largestDivisibleSubset ( vector < int >& nums ) {
sort ( nums . begin (), nums . end ());
int n = nums . size ();
int f [ n ];
int k = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
f [ i ] = 1 ;
for ( int j = 0 ; j < i ; ++ j ) {
if ( nums [ i ] % nums [ j ] == 0 ) {
f [ i ] = max ( f [ i ], f [ j ] + 1 );
}
}
if ( f [ k ] < f [ i ]) {
k = i ;
}
}
int m = f [ k ];
vector < int > ans ;
for ( int i = k ; m > 0 ; -- i ) {
if ( nums [ k ] % nums [ i ] == 0 && f [ i ] == m ) {
ans . push_back ( nums [ i ]);
k = i ;
-- m ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 func largestDivisibleSubset ( nums [] int ) ( ans [] int ) {
sort . Ints ( nums )
n := len ( nums )
f := make ([] int , n )
k := 0
for i := 0 ; i < n ; i ++ {
f [ i ] = 1
for j := 0 ; j < i ; j ++ {
if nums [ i ] % nums [ j ] == 0 {
f [ i ] = max ( f [ i ], f [ j ] + 1 )
}
}
if f [ k ] < f [ i ] {
k = i
}
}
m := f [ k ]
for i := k ; m > 0 ; i -- {
if nums [ k ] % nums [ i ] == 0 && f [ i ] == m {
ans = append ( ans , nums [ i ])
k = i
m --
}
}
return
}
GitHub