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

Bertha 。 2022-02-23 03:18 200阅读 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 条评论，200人围观）

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

相关阅读

相关 C++动态规划------最大子段和的问题

目录最大子段和（动态规划C++）最大子段和的动态规划算法 4.4 最大子段和算法4.7计算最大子段和的动态规划算法算法4.8计算最大子段和的动态规划算法的

深藏阁楼爱情的钟/ 2024年03月22日 12:11/ 0 赞/ 44 阅读

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

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

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

相关 368. 最大整除子集

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

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

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

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

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

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

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

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

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

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

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

相关动态规划（最大公共子序列）

> 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也

客官°小女子只卖身不卖艺/ 2022年06月05日 08:56/ 0 赞/ 152 阅读

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

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

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

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

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

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

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

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

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