# 0368. Largest Divisible Subset
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/largest-divisible-subset/
## 思路
状态定义：照抄问题 **dp[i] => s[1:i]里以s[i]结尾的、满足题意的最大子集的元素数目**。
状态的转移：寻找最优的前驱状态j，将dp[i]与dp[j]产生联系。
再用一个prev数组记录当前i元素在Largest-Divisible-Subset里之前的那个元素的位置。

## Code

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        Arrays.fill(prev, -1);
        Arrays.fill(dp, 1);
        Arrays.sort(nums);
        List<Integer> ans = new ArrayList<>();
        int maxSize = 0, maxIdx = 0;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(nums[i]%nums[j]==0){
                    if(dp[j]+1>dp[i]) prev[i] = j;
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
                if(maxSize<dp[i]) maxIdx = i;
                maxSize = Math.max(maxSize, dp[i]);
            }
        }
        
        int idx = maxIdx;
        while(idx!=-1){
            ans.add(0, nums[idx]);
            idx = prev[idx];
        }
        return ans;
    }
}