# C++ in O(n^2) time beats 99% with simple pruning

• The transition equation is the same as many other solutions:
f[i] = max_j f[j] + 1 in which nums[i]%nums[j]==0 and i > j

The key is, when enumerate j, we can use binary search to find where nums[i]/2 is, and start j there. This can prune a lot when nums[i] is large.

``````class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
if(nums.size() <= 1) return nums;
sort(nums.begin(), nums.end());
vector<int> f(nums.size(), 1);
vector<int> p(nums.size(), -1);
int m = 1, k = 0;
for(int i = 1 ; i < nums.size() ; i++) {
auto it = lower_bound(nums.begin(), nums.begin() + (i - 1), nums[i] / 2);
for(int j = (int)(it - nums.begin()) ; j >= 0 ; j--) {
if(nums[i] % nums[j] == 0 && f[i] < f[j] + 1) {
f[i] = f[j] + 1;
p[i] = j;
}
if(f[i] > m) {
m = f[i];
k = i;
}
}
}
vector<int> res(m, 0);
int i = k, j = m - 1;
while(j >= 0) {
res[j] = nums[i];
i = p[i];
j--;
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.