C++刷leetcode(368. 最大整除子集)【动态规划】

糖逗

题目描述：

1. 
   
2. 给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
   
3. 
   
4. 如果有多个目标子集，返回其中任何一个均可。
   
5. 
   
6. 
   
7. 
   
8. 示例 1:
   
9. 
   
10. 输入: [1,2,3]
    
11. 输出: [1,2] (当然, [1,3] 也正确)
    
12. 示例 2:
    
13. 
    
14. 输入: [1,2,4,8]
    
15. 输出: [1,2,4,8]

复制代码

1. vector<int> largestDivisibleSubset(vector<int>& nums) {
   
2.         vector<int> res;
   
3.         int len = nums.size();
   
4.         if(len == 0 )return res;
   
5.         sort(nums.begin(), nums.end());
   
6.         vector<int> dp(len, 0);
   
7.         dp[0]  = 1;
   
8.         for(int i = 1; i < len ; i++){
   
9.             for(int j = i-1; j>=0; j--){
   
10.                 if(nums[i] % nums[j] == 0){
    
11.                     dp[i] = max(dp[i], dp[j]+1);
    
12.                 }
    
13.             }
    
14.             if(dp[i] == 0) dp[i] = 1;
    
15.         }//dp记录以nums[i]结尾的最大长度
    
16.         int max_len = *max_element(dp.begin(), dp.end());
    
17.         int k = dp.size()-1;
    
18.         while(k >=0){
    
19.             if(max_len == 0)break;
    
20.             if(dp[k] == max_len){
    
21.                 if(res.empty() || res.back()%nums[k] == 0){
    
22.                     res.push_back(nums[k]);
    
23.                     max_len--;
    
24.                 }
    
25.                
    
26.             }
    
27.             k--;
    
28.         }//根据dp返回结果
    
29.         return res;
    
30.     }

复制代码