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:
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]
方法
一开始上来这个题目直观的就是使用动态规划，可是在集合中判断两两是否模为0，可能两个数位置相差很大，很难找到状态转换方程。找到转换方程的诀窍就是，对集合由大到小排序，因为若a%b=0,b%c=0 ==> a%c=0，排序后可以保证若当前数与前一某个数能取模为0，那么他可以满足与那个数的所有符合取模为0的数取模为0。即找到状态转换方程，dp[i]表示在i点上能与之前的数互相取模的最大数量：
dp[i] = max(dp[i],dp[j]+1),(j<i,num[i]%num[j]==0)
同时该题目又要求打印所有节点，所以还需要另外一个一维数组，存储在位置i的前一个满足num[i]%num[j]==0的地址，所以实际上该题也可以使用二维数组，一起存储dp[]和pre[]，最后根据pre[i]的地址打印，此题result==dp,result[i]初始都为1，pre[i]初始都为-1
谨记
在此题中，最后一个数并不代表它与其他数取模的个数最多如{2,4,8,11},11并不能与其他数取余，所以还需要每次遍历时判断max和maxIndex,pre[i]从maxIndex开始出发。
public class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
int length = nums.length;
Arrays.sort(nums);
int[] result = new int[length];
List<Integer> res = new ArrayList<Integer>();
int[] pre = new int[length];
int max = 0;
int maxIndex = -1;
for(int i = 0; i < length; i++){
result[i] = 1;
pre[i] = -1;
for(int j = i-1; j >= 0; j--){
if(nums[i]%nums[j] == 0){
if(result[j] + 1 > result[i]){
result[i] = result[j]+1;
pre[i] = j;
}
}
}
if(result[i] > max){
max = result[i];
maxIndex = i;
}
}
while(maxIndex != -1){
res.add(nums[maxIndex]);
maxIndex = pre[maxIndex];
}
return res;
}
}