佛山专业做网站公司有哪些,建设搜索引擎友好的网站,建设部网站刘赵云,网易企业邮箱登录入口登录入口给你一个由 无重复 正整数组成的集合 nums #xff0c;请你找出并返回其中最大的整除子集 answer #xff0c;子集中每一元素对 (answer[i], answer[j]) 都应当满足#xff1a; answer[i] % answer[j] 0 #xff0c;或 answer[j] % answer[i] 0,如果存在多个有效解子集请你找出并返回其中最大的整除子集 answer 子集中每一元素对 (answer[i], answer[j]) 都应当满足 answer[i] % answer[j] 0 或 answer[j] % answer[i] 0,如果存在多个有效解子集返回其中任何一个均可。
示例 1
输入nums [1,2,3] 输出[1,2] 解释[1,3] 也会被视为正确答案。 示例 2
输入nums [1,2,4,8] 输出[1,2,4,8]
提示
1 nums.length 1000 1 nums[i] 2 * 109 nums 中的所有整数 互不相同
将输入序列按照从小到大排列
设 A i A_i Ai为含有 m u n s [ i ] muns[i] muns[i]为最大整数的最大整除集合则可以知道若 a i a j a_ia_j aiaj且 a i % a j 0 a_i \% a_j0 ai%aj0则 A j ⊂ A i A_j\sub A_i Aj⊂Ai
设dp[i]为集合 A i A_i Ai中元素的个数
最优子结构dp[i]
状态转移方程dp[i] max(dp[i], dp[j] 1)其中 j i ji ji且 m u n s [ i ] % n u m [ j ] 0 muns[i]\%num[j]0 muns[i]%num[j]0
vectorint largestDivisibleSubset(vectorint nums) {int index 0, max_len;int l nums.size();sort(nums.begin(), nums.end());vectorint dp vectorint(l, 1);vectorint res vectorint();for (int i 0; i l; i) {for (int j 0; j i; j) {if (nums[i] % nums[j] 0) {dp[i] max(dp[i], dp[j] 1);}}if (dp[i] dp[index]) {index i;}}max_len dp[index];res.push_back(nums[index]);for (int i index - 1; i 0 max_len 0; i--) {if (nums[index] % nums[i] 0 dp[i] max_len - 1) {res.push_back(nums[i]);index i;max_len--;}}sort(res.begin(), res.end());return res;
}
