首页 > 代码库 > 最长可除序列
最长可除序列
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
.
Example
Given nums = [1,2,3]
, return [1,2]
or [1,3]
Given nums = [1,2,4,8]
, return [1,2,4,8]
类似最长增长子序列。需要返回子序列,刚开始想到把每种可能都存在单独的list里,并不是很优化的做法。只需找到最长的那个可除序列,再遍历一遍,把数都存在list里面即可;
本题亮点是用到了回溯。所以,除了需要dp数组外,还需要额外的pre数组记录每个数的前继点。
首先,对数组排序,正序逆序都无所谓吧,不排序太复杂了;这里采用正序。
dp[i]表示,arr[i]能整除前面1~i-1个数的个数。递推过程是,if nums[i] % nums[j] == 0 , dp[i] = max{dp[i], dp[j] + 1}, j < i
初始条件,dp[i] = 1; pre[i] = -1; 表示每个数在开算之前,长度最少为1, 前继至少是-1;
同时,需要全局变量记录出现最大序列长度的位置。
public static List<Integer> largestDivisibleSubset(int[] nums) { // Write your code here List<Integer> list = new ArrayList<>(); if(nums == null || nums.length == 0) return list; Arrays.sort(nums); int len = nums.length; int[] dp = new int[len]; int[] pre = new int[len]; int max = 0, index = -1; for(int i = 0; i < len; i++){ dp[i] = 1; pre[i] = -1; for(int j = i-1; j >= 0; j--){ if(nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]){ dp[i] = dp[j] + 1; pre[i] = j; } } if(dp[i] > max){ max = dp[i]; // 更新最大值位置 index = i; } } while(index != -1){ list.add(nums[index]); // 回溯找到每个数 index = pre[index]; } return list; }
最长可除序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。