# LeetCode 368. 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:

image.png Example 2:

image.png

# 代码

public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int n = nums.length;
int[] count = new int[n];
int[] pre = new int[n];
Arrays.sort(nums);
int max = 0, index = -1;
for (int i = 0; i < n; i++) {
count[i] = 1;
pre[i] = -1;
for (int j = i - 1; j >= 0; j--) {
if (nums[i] % nums[j] == 0) {
if (1 + count[j] > count[i]) {
count[i] = count[j] + 1;
pre[i] = j;
}
}
}
if (count[i] > max) {
max = count[i];
index = i;
}
}
List<Integer> res = new ArrayList<>();
while (index != -1) {
index = pre[index];
}
return res;
}
}

0 条评论

## 相关文章

267100

### Leetcode 200 Number of Islands 岛的个数

1. 遍历每一个结点，如果某结点是陆地且未访问过，岛数目加1，修改未访问标志位，然后把该点放入队列中，以备扩展岛屿使用，进入2 2. 队列不为空时，取出点，然...

34430

### Java 常见内存溢出异常与代码实现

Java 堆 OutOfMemoryError Java 堆是用来存储对象实例的, 因此如果我们不断地创建对象, 并且保证 GC Root 和创建的对象之间...

22180

6210

9510

8520

### Bessie的好牌（队列）- POJ 3629

Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

15630

23890

### Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼，一时还真不知道怎么解释，能让完全没有接触过的人都能听懂 列表，什么是列表呢？ 好比你到了一个村里，看...

23280

22970