Greedy Algorithm
Approach\n1. len = 1\n\nWe can get the result num[0]^2\n\n2. len = 2\n\nAssume [a*b, a*c] where LCM = a, GCD = a*b*c. Then res = a*a*b*c = (a*b) * (a*c).\nIf we
# Approach\n1. `len = 1`\n\nWe can get the result `num[0]^2`\n\n2. `len = 2`\n\nAssume `[a*b, a*c]` where `LCM = a`, `GCD = a*b*c`. Then `res = a*a*b*c = (a*b) * (a*c)`.\nIf we choose to remove smaller one `(a*b)`, then `res = (a*c) * (a*c)` .\n\nSince `a*b < a*c`, we can know that the best strategy is to remove the smaller num.\n\n3. `len >= 3`\n\nAssume it is sorted array `[abce, abdf, acdg] (bce <= bdf <= cdg)`\n\n a. If no remove: `LCM = a, GCD = abcdefg -> res = aabcdefg`\n b. If remove `abce`: `LCM = ad, GCD = abcdfg -> res = aabcddfg`\n c. If remove `abdf`: `LCM = ac, GCD = abcdeg -> res = aabccdeg`\n d. If remove `acdg`: `LCM = ab, GCD = abcdef -> res = aabbcdef`\n\nFrom the above comparison, we can see it is difficult to identify which result will give the max value. Hence simply greedy algorithm doesn\'t work, which is to remove the smallest element and then get the LCM/GCD.\n\n- `650 / 752 testcases passed` if adopting removing the smallest number.\n- `746 / 752 testcases passed` if also comparing the result from LCM/GCD if there is not any removed element.\n- `All testcases passed` if we fully compare all possible candidates.\n\n# Complexity\n- Time complexity:\n`O(N^2)`\n\n# Code\n```java []\nclass Solution {\n    public long maxScore(int[] nums) {\n        if (nums.length == 1) {\n            long n = (long) nums[0];\n            return n*n;\n        }\n\n        Arrays.sort(nums);\n\n        long lcm = (long) nums[0];\n        long gcd = (long) nums[0];\n\n        for (int i = 1; i < nums.length; i++) {\n            long n = (long) nums[i];\n            lcm = getLcm(n, lcm);\n            gcd = n * gcd / getLcm(gcd, n);\n        }\n\n        long res = lcm * gcd;\n\n        for (int i = 0; i < nums.length; i++) {\n            res = Math.max(res, getProduct(nums, i));\n        }\n\n        return res;\n    }\n\n    private long getLcm(long a, long b) {\n        if (a < b) {\n            return getLcm(b, a);\n        }\n\n        while (a % b > 0) {\n            long r = a % b;\n            a = b;\n            b = r;\n        }\n\n        return b;\n    }\n\n    private long getProduct(int[] nums, int skipIdx) {\n        long lcm = skipIdx == 0 ? (long) nums[1] : (long) nums[0];\n        long gcd = skipIdx == 0 ? (long) nums[1] : (long) nums[0];\n\n        for (int i = 0; i < nums.length; i++) {\n            if (i == skipIdx) continue;\n\n            long n = (long) nums[i];\n            lcm = getLcm(n, lcm);\n            gcd = n * gcd / getLcm(gcd, n);\n        }\n\n        return lcm * gcd;\n    }\n}\n```
['Greedy', 'Java']