本教學將討論一個問題，其中給定一個不同的正整數陣列。我們需要找到最大的子集，使得每對較大的元素除以較小的元素，例如-
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中文網其他相關文章！
