C++ 程序查找数组中最大的可整除子集
c++server side programmingprogramming
本教程将讨论一个问题，给定一个不同的正整数数组。我们需要找到最大的子集，使得每对较大的元素都被较小的元素除，例如 −
输入:nums[ ] = { 1, 4, 2, 6, 7}
输出:1 2 4
解释:
所有可整除子集为:(1, 2, 4)、(1, 2, 6)、(1, 7) 等
我们有 2 个长度为 3 的子集，其中所有对都满足条件。
输入:nums[ ] = { 1, 2, 3, 6 }
输出:6 2 1
寻找解决方案的方法
在本教程中，我们将解释两种不同的方法。
简单方法
在一个简单的方法中，我们可以应用递归来解决这个问题。我们将获取每个元素并检查它是否应该包含在子集中。假设我们从第一个元素开始。我们将有两个选项，要么将第一个元素包含在子集中，要么不包含在子集中。让我们包括第一个元素。然后，对于要包含在子集中的第二个元素，它应该可以被子字符串中的元素(即第一个元素)整除或整除。这就是我们遍历数组的方式。因此将有 2^n 条可能的路径，这将产生 O(2^n) 的时间复杂度。让我们看看解决这个问题的可行方法。
有效方法
可以使用动态规划来解决这个问题。
对数组进行排序，使左侧元素可以被正确元素整除。我们必须检查一次可整除性。
我们将采用最长递增子序列，即我们的 dp[ ] 数组，来存储直到第 i 个索引的最大可整除子集。我们将用 1 初始化每个索引，因为每个元素都会整除自身。
现在我们将从第二个索引开始迭代，并检查每个元素是否为以当前索引结尾的最大可整除子集。这样，我们将找到每个索引的最大子集。
现在遍历数组，为每个元素找到一个可整除计数最大的除数。并将当前索引的可整除计数值更改为该元素的可整除计数 + 1。
示例
上述方法的 C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 2, 3, 6};
int n = sizeof(nums)/sizeof(int);
// 对数组进行排序以排除一个除法条件。
sort(nums, nums+n);
vector <int> prev_res(n, -1);
// 用于存储所有元素除数的向量
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){ // 检查第 j 个索引处是否存在第 i 个元素的除数。
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
// 检查添加是否会增加子序列中的元素数量。
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
// 查找具有最大子集数量的索引。
if(max<dp[i])
max = dp[i];
}
cout << "数组中最大的可整除子集:";
// 打印最大子集
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
}
输出
数组中最大的可整除子集:6 2 1
结论
在本教程中，我们讨论了一个问题:我们需要在给定数组中找到最大的可整除子集，其中每对中的整数都是可整除的。我们讨论了一种递归方法，它会产生指数时间复杂度，因此我们讨论了一种动态规划解决方案。我们还讨论了这个问题的 C++ 程序，我们可以使用 C、Java、Python 等编程语言来完成。我们希望本教程对您有所帮助。
