leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0368.cpp (851B)

      1 class Solution {
      2   public:
      3     vector<int> largestDivisibleSubset(vector<int> &nums) const {
      4         sort(begin(nums), end(nums));
      5 
      6         static int len[1001], parent[1001];
      7         memset(len, 0x00, sizeof(len));
      8 
      9         int maxi = 0, idx = -1;
     10         for (int i = size(nums) - 1; i >= 0; i--) {
     11             for (int j = i; j < size(nums); j++) {
     12                 if (nums[j] % nums[i] == 0 && len[i] < 1 + len[j]) {
     13                     len[i] = 1 + len[j];
     14                     parent[i] = j;
     15 
     16                     if (len[i] > maxi) {
     17                         maxi = len[i];
     18                         idx = i;
     19                     }
     20                 }
     21             }
     22         }
     23 
     24         vector<int> res(maxi);
     25         for (int i = 0; i < maxi; i++) {
     26             res[i] = nums[idx];
     27             idx = parent[idx];
     28         }
     29 
     30         return res;
     31     }
     32 };