本教程将讨论一个问题,其中给定一个不同的正整数数组。我们需要找到最大的子集,使得每对较大的元素除以较小的元素,例如 -
Input: nums[ ] = { 1, 4, 2, 6, 7} Output: 1 2 4 Explanation: All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc We have 2 subsets of length 3 in which all the pairs satisfy the condition. Input: nums[ ] = { 1, 2, 3, 6 } Output: 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); // sorting the array to exclude one condition for division. sort(nums, nums+n); vector <int> prev_res(n, -1); // vector to store divisors of all the elements vector <int> dp(n, 1); int max = 1; for (int i=1; i<n; i++){ // Check if there's a divisor of ith element present at jth index. for (int j=0; j<i; j++){ if (nums[i]%nums[j] == 0){ // check If adding that increases the number of elements in subsequence. if (dp[i] < dp[j] + 1){ dp[i] = dp[j]+1; prev_res[i] = j; } } } // finding index having a maximum number of subsets. if(max<dp[i]) max = dp[i]; } cout << "Largest divisible subset in the array: "; // printing the maximum subset int k = max; while (k >= 0){ cout << nums[k] << " "; k = prev_res[k]; } return 0; }
Largest divisible subset in the array: 6 2 1
在本教程中,我们讨论了一个问题:我们需要找到给定数组中每对整数可整除的最大可整子集。我们讨论了一种产生指数时间复杂度的递归方法,因此我们讨论了动态编程解决方案。我们还讨论了解决此问题的 C++ 程序,我们可以使用 C、Java、Python 等编程语言来实现。我们希望本教程对您有所帮助。
以上是C++程序:在数组中找到最大的可整除子集的详细内容。更多信息请关注PHP中文网其他相关文章!