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

Bertha 。 2022-02-23 03:18 254阅读 0赞

## 来自LeetCode 368 ##

描述

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。  
如果有多个目标子集，返回其中任何一个均可。  
此题类似于求最长递增子序列  
[http://www.omegaxyz.com/2017/05/12/longest\_ascending\_sequence/][http_www.omegaxyz.com_2017_05_12_longest_ascending_sequence]

class Solution {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums) {
            vector<int> ans;
            if(nums.size() == 0)return ans;
            sort(nums.begin(), nums.end());
            int maxlen = 0;
            vector<int> longest(nums.size(), 1);
            vector<int> cnt(nums.size()+1, 0);
            cnt[nums.size()] = 0;
            for(int i = 1; i < nums.size(); i++){
                for(int j = 0; j < i; j++){
                    if(nums[i] % nums[j] == 0){
                        if(longest[i] < longest[j] + 1)longest[i] = longest[j] + 1;
                    }
                }
            }
            for(int i = 0; i < nums.size(); i++){
                if(cnt[longest[i]] == 0)cnt[longest[i]] = nums[i];
                if(maxlen < longest[i])maxlen = longest[i];
            }
            for(int i = 1; i <= maxlen; i++)ans.push_back(cnt[i]);
            return ans;
        }
    };

[更多内容访问omegaxyz.com][omegaxyz.com]  
网站所有代码采用Apache 2.0授权  
网站文章采用知识共享许可协议BY-NC-SA4.0授权  
© 2019 • OmegaXYZ-版权所有 转载请注明出处

[http_www.omegaxyz.com_2017_05_12_longest_ascending_sequence]: http://www.omegaxyz.com/2017/05/12/longest_ascending_sequence/
[omegaxyz.com]: http://xn--omegaxyz-on6m893d6sgwn0bu73h213a.com

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 368. 最大整除子集

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

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

相关最大正方形(动态规划)

最大正方形难度中等在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1

Dear 丶/ 2023年03月12日 12:25/ 0 赞/ 21 阅读

相关动态规划c语言最大子数组之和,动态规划连续子数组的最大和

题目输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1: 输入: num

- 日理万妓/ 2022年10月14日 15:53/ 0 赞/ 241 阅读

相关 368. 最大整除子集

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

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

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

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

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

相关动态规划——最大累加和

动态规划？ Time Limit: 1000MS Memory Limit: 65536KB Problem Description 动态规划作为《运筹学》的一个分支

一时失言乱红尘/ 2022年07月13日 15:27/ 0 赞/ 201 阅读

相关最大子矩阵（动态规划）

最大矩阵和顾名思义，就是一个矩阵和最大，例如下面的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 最终找

忘是亡心i/ 2022年06月07日 12:50/ 0 赞/ 379 阅读

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

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

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

相关最大子矩阵最大子数组动态规划

最大子矩阵最大子数组动态规划最大子矩阵问题也是动态规划中经典的一道题目（感觉自己到目前为止接触到的只是动态规划的冰山一角，区间dp、数位dp… 还是要花时间

旧城等待，/ 2022年03月15日 04:16/ 0 赞/ 349 阅读

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

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

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