# Solution using 2 maps in C++ with comments, 256 ms

• Optimization:

``````1. use size_map to record vector size, iterate from longer vector to shorter vector
2. only check last item of each vector, no need to check preview ones
3. use result_map to record vector result, to reduce vector copy.

class Solution {
// size of vector -> set of last item of vector
map<int, set<int>> size_mp;
// last item of vector -> whole vector
map<int, vector<int>> result_mp;

public:
// if new item can be divided by last item, so be all items in vector,
// so that no need to check previous item
vector<int> largestDivisibleSubset(vector<int>& nums) {
if (nums.size() < 1) {
return nums;
}

sort(nums.begin(), nums.end());

for (vector<int>::iterator itr = nums.begin();
itr != nums.end(); ++itr) {

// only need prev item to get whole items from result_mp
int prev = -1;

// iterator from longer vector to shorter
for (map<int, set<int>>::reverse_iterator ritr = size_mp.rbegin();
ritr != size_mp.rend(); ++ritr) {

for (set<int>::iterator sitr = ritr->second.begin();
sitr != ritr->second.end(); ++sitr) {

// if last item of long vector can divide new number,
// no need to check other vector or previous item
if (*itr % *sitr == 0) {
prev = *sitr;
break;
}
}
if (prev != -1) {
break;
}
}

// add current result to result_mp
vector<int> tmp_vec;
if (prev != -1) {
tmp_vec = result_mp[prev];
}
tmp_vec.push_back(*itr);
result_mp[*itr] = tmp_vec;
int newsize = tmp_vec.size();

// add current result to size_mp
if (size_mp.find(newsize) == size_mp.end()) {
set<int> tmp_set;
tmp_set.insert(*itr);
size_mp[newsize] = tmp_set;
}
else {
size_mp[newsize].insert(*itr);
}

}

set<int>::iterator sitr_new = size_mp.rbegin()->second.begin();
return result_mp[*sitr_new];

}

};``````

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