leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0368.cpp (851B)

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