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]
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.
问题分析：
动态规划思路与LIS问题基本一致，首先将数组进行排序，然后依次遍历每一个元素，确定以该元素为结尾的LDS长度（寻找该元素前面的所有可以被整除的元素的LDS最大值，在此基础上加1）。
此时时间复杂度为基本代码如下：
public class Solution { public List largestDivisibleSubset(int[] nums) { List rst = new LinkedList<>(); if (nums == null || nums.length == 0) return rst; Arrays.sort(nums); rst.add(nums[0]); Map > map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { List temp = new LinkedList<>(); temp.add(nums[i]); map.put(nums[i], temp); } for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] % nums[j] == 0 && map.get(nums[j]).size() + 1 > map.get(nums[i]).size()) { List temp = new LinkedList<>(map.get(nums[j])); temp.add(nums[i]); map.put(nums[i], temp); } } if (rst.size() < map.get(nums[i]).size()) rst = map.get(nums[i]); } return rst; }} 以上代码AC了，但是效率很低。可以看出时间复杂度为O(n^2)，空间复杂度为O(n^2)。
问题优化：
上述解法空间复杂度很高，利用map直接把所有的结果都记录了下来。仔细思考会发现，可以通过记录每一步的上一个数组下标来将空间复杂度降低到O(n)。
改进后代码如下，其中rec数组用来记录以特定下标为最后一个元素的LDS长度，index数组用来记录以特定下标为最后一个元素的LDS的上一个元素下标。last_index用来记录最终结果的最后一个元素下标，max_length用来记录最终LDS长度。
public class Solution { public List largestDivisibleSubset(int[] nums) { List rst = new LinkedList<>(); if (nums == null || nums.length == 0) return rst; int[] rec = new int[nums.length]; int[] index = new int[nums.length]; int last_index = 0; int max_length = 1; Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { rec[i] = 1; index[i] = -1; } for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] % nums[j] == 0 && rec[j] + 1 > rec[i]) { rec[i] = rec[j] + 1; index[i] = j; } } if (rec[i] > max_length) { max_length = rec[i]; last_index = i; } } while (last_index >= 0) { rst.add(nums[last_index]); last_index = index[last_index]; } return rst; }} 这种解法时间复杂度为O(n^2)，空间复杂度为O(n)。击败96.88%submissions。