368. Largest Divisible Subset

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> dp(n,0), parent(n,0), ret ;
        int mx = 0, mx_idx = 0;
        for(int i=n-1 ; i>-1;i--){
            for(int j=i ; j<n;j++){
                if(nums[j]%nums[i] == 0 && dp[i] < dp[j]+1){
                    dp[i] = dp[j]+1;
                    parent[i] = j;
                    if(mx<dp[i]){
                        mx = dp[i];
                        mx_idx = i;
                    }
                }
            }
        }
        for(int i=0;i<mx ; ++i){
            ret.push_back(nums[mx_idx]);
            mx_idx = parent[mx_idx];
        }
        return ret;
                                    
        
        
    }
};

analysis

  • time complexity O(n^2)
  • space complexity O(n)