leetcode

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