[LintCode] 603 Largest Divisible Subset 解题报告

Description
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.


Notice
If there are multiple solutions, return any subset is fine.



Example
Given nums = [1,2,3], return [1,2] or [1,3]

Given nums = [1,2,4,8], return [1,2,4,8]



思路
DP。
f[i]：以nums[i]作为Largest Divisible Subset的最后一个元素的集合的最大值。
lastIndex[i]：以nums[i]作为Largest Divisible Subset的最后一个元素的集合的上一个元素的index。




Code

public class Solution {
    /**
     * @param nums a set of distinct positive integers
     * @return the largest subset 
     */
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // Write your code here
        
        int[] f = new int[nums.length];
        int[] lastIndex = new int[nums.length];
        Arrays.sort(nums);
        
        int max = 0;
        int maxIndex = -1;
        
        for (int i = 0; i < nums.length; i++) {
            f[i] = 1;
            lastIndex[i] = -1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && f[i] < f[j] + 1) {
                    f[i] = f[j] + 1;
                    lastIndex[i] = j;
                }
            }
            if (f[i] > max) {
                max = f[i];
                maxIndex = i;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (maxIndex != -1) {
            result.add(nums[maxIndex]);
            maxIndex = lastIndex[maxIndex];
        }
        
        return result;
    }
}