Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
<pre>
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
</pre>
Example 2:
<pre>
nums: [1,2,4,8]
Result: [1,2,4,8]
</pre>
解體思路
首先我們根據(jù)條件Si % Sj = 0 or Sj % Si = 0可以推出简珠，最大可整除子集中任意兩個數(shù)一定有一個數(shù)可以被可以另一個數(shù)整除。
也就是說，將這些數(shù)按從小到大的順序排列舌劳，則后一個數(shù)一定可以被前一個數(shù)整除!
于是問題轉換為了類似于最長不下降子序列的DP指巡。
代碼
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(),nums.end());
int len = nums.size();
int ans = 0, ansi;
int dp[len];
int pre[len];//用于保存最長可整除序列的路徑
for (int i=0;i<len;i++){
dp[i] = 1;
pre[i] = -1;
for (int j=0;j<i;j++){
if (nums[i]%nums[j] == 0 && dp[j]+1>dp[i]){
dp[i] = dp[j]+1; pre[i] = j;
}
}
if (dp[i] > ans){
ans = dp[i]; ansi = i;
}
}
//找出最長可整除子序列菊匿，方法類似于最長不下降子序列
vector<int> res;
for (int i=1;i<=ans;i++){
res.push_back(nums[ansi]); ansi = pre[ansi];
}
//利用pre數(shù)組找到最長可整除子序列
sort(res.begin(),res.end());
return res;
}
};
