leetcode 368. 最大整除子集

雨点打透心脏的1/2处 2023-07-03 08:16 8阅读 0赞

思路：其实和最长上升子序列的思路基本一致。

dp\[i\]表示以nums\[i\]结尾的最大的整数子集。dp\[i\]=max(dp\[j\]+1,dp\[i\]) 其中nums\[j\]%nums\[i\]==0||nums\[i\]%nums\[j\]==0

为了避免6 2 4 这样的序列出现，只需先对nums进行一下排序即可。

需要输出子集，那么只要开一个path数组，记录一下路径即可。

class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            int n=nums.size();
            vector<int> vec;
            if(n<1) return vec;
            int dp[n+1];
            int path[n+1];
            sort(nums.begin(),nums.end());
            dp[0]=0;
            for(int j=1;j<=n;j++){
                path[j]=j;
                dp[j]=1;
            }
            int index=0;
            int M=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<i;j++)
                {
                    if(nums[i-1]%nums[j-1]==0||nums[j-1]%nums[i-1]==0)
                    {
                        if(dp[j]+1>dp[i]){
                            path[i]=j;
                        }
                        dp[i]=max(dp[j]+1,dp[i]);
                    }
                }
                if(dp[i]>M)
                {
                    M=dp[i];
                    index=i;
                }
            }
            vec.push_back(nums[index-1]);
            while(path[index]!=index)
            {
                vec.push_back(nums[path[index]-1]);
                index=path[index];
            }
            return vec;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode：子集

定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: nums = [1,2,3]...

女爷i/ 2024年04月17日 05:58/ 0 赞/ 74 阅读

相关 leetcode 368. 最大整除子集

思路：其实和最长上升子序列的思路基本一致。 dp\[i\]表示以nums\[i\]结尾的最大的整数子集。dp\[i\]=max(dp\[j\]+1,dp\[i\]) 其中nu

雨点打透心脏的1/2处/ 2023年07月03日 08:16/ 0 赞/ 9 阅读

相关 leetcode：子集

子集一个正在努力爱好运动的程序猿座右铭：越努力越幸运，越运动越健康，热爱编程，热爱运动。记录学习算法这段日子。 -------------------

男娘i/ 2022年12月22日 04:55/ 0 赞/ 194 阅读

相关 368. 最大整除子集

> 给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer\[i\], answer\[j\])

向右看齐/ 2022年10月09日 12:15/ 0 赞/ 148 阅读

相关最大团问题和最大独立子集

不要去百度百科找最大团，因为你会找到一个团购网站= = 维基百科：https://en.wikipedia.org/wiki/Clique\_problem 首先，团是什

迷南。/ 2022年09月04日 08:50/ 0 赞/ 199 阅读

相关 leetcode 368. Largest Divisible Subset | 368. 最大整除子集（动态规划详解）

题目 [https://leetcode.com/problems/largest-divisible-subset/][https_leetcode.com_probl

Myth丶恋晨/ 2022年08月29日 13:59/ 0 赞/ 138 阅读

相关 leetcode 368. Largest Divisible Subset 最大分割子集+LISS最长递增子序列+动态规划DP

Given a set of distinct positive integers, find the largest subset such that every pair

落日映苍穹つ/ 2022年06月07日 02:45/ 0 赞/ 163 阅读

相关动态规划---最大和的子集

1、题目： Given an integer array `nums`, find the contiguous subarray (containing at least

雨点打透心脏的1/2处/ 2022年05月23日 07:47/ 0 赞/ 175 阅读

相关【LeetCode】368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair

﹏ヽ暗。殇╰゛Y/ 2022年04月18日 03:35/ 0 赞/ 173 阅读

相关动态规划——最大整除子集C++

来自LeetCode 368 描述给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 S

Bertha 。/ 2022年02月23日 03:18/ 0 赞/ 248 阅读