05 August 2008
正整数数组找到subsets满足以下条件
1
2
answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
返回任意一个subset
类似LIS的DP
1
2
3
4
1. Sort
2. Find the length of longest subset
3. Record the largest element of it.
4. Do a loop from the largest element to nums[0], add every element belongs to the longest subset.
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
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
Arrays.sort(nums); // 需要排序
int len = nums.length;
//以当前元素为结尾，最大的可相互整个mod的子数组,这里不用len + 1
int[] dp = new int[len];
//这个数组是为了记录最大子数组里面有哪些元素
int[] pre = new int[len];
int maxLenIndex = 0;
int index = -1;
for (int i = 0; i < len; i++) {
dp[i] = 1; //初始化为1，就是自己
pre[i] = -1; //前面最长的暂定为-1
for (int j = i - 1; j >= 0; j--) { //往当前元素的前面找
if (nums[i] % nums[j] == 0) {
if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
}
if (dp[i] > maxLenIndex) {
maxLenIndex = dp[i];
index = i;
}
}
while (index != -1) {
result.add(nums[index]);
index = pre[index];
}
return result;
}
}