package com.heu.wsq.leetcode.dp;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 368. 最大整除子集
* @author wsq
* @date 2021/4/23
* 给你一个由 无重复 正整数组成的集合 nums ,请你找出并返回其中最大的整除子集 answer ,子集中每一元素对 (answer[i], answer[j]) 都应当满足:
* answer[i] % answer[j] == 0 ,或
* answer[j] % answer[i] == 0
* 如果存在多个有效解子集,返回其中任何一个均可。
*
* 示例 1:
* 输入:nums = [1,2,3]
* 输出:[1,2]
* 解释:[1,3] 也会被视为正确答案。
*
* 链接:https://leetcode-cn.com/problems/largest-divisible-subset
*/
public class LargestDivisibleSubset {
public List<Integer> largestDivisibleSubset(int[] nums){
int n = nums.length;
if(n == 0){
return null;
}
// 排序数组
Arrays.sort(nums);
// 状态数组,f[i]表示以索引i对应元素结尾的 最大 子集长度
// 最后一步:f[i] = Math.max(f[i], f[j] + 1), f[j]是f[i]能整除的元素
// 子问题:f[i]从众多能整除的元素中f[j]选出“最大子集长度”的元素
int[] f = new int[n];
// 情况和边界值,每个元素自身能够构成长度为1的整除子集
Arrays.fill(f, 1);
// 用于进行回推路径使用
// 整除子集 的最大值
int maxCount = 0;
// 最大子集的最后一位对应的最大数
int maxNum = 0;
// 状态转移求解
for(int i = 1; i < n; i++){
for(int j = i-1; j >= 0; j--){
if(nums[i] % nums[j] == 0){
f[i] = Math.max(f[i], f[j] + 1);
}
}
if(f[i] > maxCount){
maxCount = f[i];
maxNum = nums[i];
}
}
// 回推 求解整数子集的路径
List<Integer> ans = new ArrayList<>();
// 根据最大值对应的数,进行路径检索
if(maxCount == 1){
ans.add(nums[0]);
return ans;
}
for(int i = n - 1; i >= 0; i--){
if(f[i] == maxCount && maxNum % nums[i] == 0){
ans.add(0, nums[i]);
maxNum = nums[i];
maxCount--;
}
}
return ans;
}
}