My 86ms C++ solution


  • 0
    L

    class Solution {
    public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
    vector<int> result;
    int size = nums.size();
    if (size == 0) {
    return result;
    }
    sort(nums.begin(), nums.end());
    vector<pair<int, int> > f(size, make_pair(1, -1)); // first : length, second : index
    int id = 0;
    int maxlen = 1;
    for (int i = 0; i < size; i++) {
    for (int j = 0; j < i; j++) {
    if (nums[i] % nums[j] == 0 && f[i].first <= f[j].first + 1) {
    f[i].first = f[j].first + 1;
    f[i].second = j;
    }
    }
    if (maxlen < f[i].first) {
    id = i;
    maxlen = f[i].first;
    }
    }
    // trace back;
    while (id != -1) {
    result.push_back(nums[id]);
    id = f[id].second;
    }
    reverse(result.begin(), result.end());
    return result;
    }
    };


Log in to reply
 

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