leetcode

commit 4f66e7b9daf59fc73f88368aa6769770753f1445
parent 4fcdba0d6ecb25b0f3ac6b70de3109fce8c4b005
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  9 Feb 2024 22:42:46 +0000

Daily Problem

Diffstat:
A
Problems/0368.cpp
 | 
32
++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 33 insertions(+), 0 deletions(-)
diff --git a/Problems/0368.cpp b/Problems/0368.cpp
@@ -0,0 +1,32 @@
+class Solution {
+  public:
+    vector<int> largestDivisibleSubset(vector<int> &nums) const {
+        sort(begin(nums), end(nums));
+
+        static int len[1001], parent[1001];
+        memset(len, 0x00, sizeof(len));
+
+        int maxi = 0, idx = -1;
+        for (int i = size(nums) - 1; i >= 0; i--) {
+            for (int j = i; j < size(nums); j++) {
+                if (nums[j] % nums[i] == 0 && len[i] < 1 + len[j]) {
+                    len[i] = 1 + len[j];
+                    parent[i] = j;
+
+                    if (len[i] > maxi) {
+                        maxi = len[i];
+                        idx = i;
+                    }
+                }
+            }
+        }
+
+        vector<int> res(maxi);
+        for (int i = 0; i < maxi; i++) {
+            res[i] = nums[idx];
+            idx = parent[idx];
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -285,6 +285,7 @@ for solving problems.
 |  0350  |    Easy    | [Intersection of Two Arrays II](Problems/0350.cpp)                                                 |
 |  0352  |    Hard    | [Data Stream as Disjoint Intervals](Problems/0352.cpp)                                             |
 |  0367  |    Easy    | [Valid Perfect Square](Problems/0367.cpp)                                                          |
+|  0368  |   Medium   | [Largest Divisible Subset](Problems/0368.cpp)                                                      |
 |  0371  |   Medium   | [Sum of Two Integers](Problems/0371.cpp)                                                           |
 |  0373  |   Medium   | [Find K Pairs with Smallest Sums](Problems/0373.cpp)                                               |
 |  0374  |    Easy    | [Guess Number Higher or Lower](Problems/0374.cpp)                                                  |