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


  • 0
    U

    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;
        }
    };
    

Log in to reply
 

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