Java | DP | time O(N) | Beats 100.00%
Intuition\n Describe your first thoughts on how to solve this problem. \nif we want to calculate the factor score which removed nums[i],\nwe need prefix[i-1] an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nif we want to calculate the **factor score** which removed `nums[i]`,\nwe need `prefix[i-1]` and `suffix[i+1]`\n```text\nprefix[i-1]    suffix[i+1]\n[x x x x]   x  [x x x x]\n            i  \n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. calculate all `prefix[i]` for GCD and LCM\n2. go backward to calculate `suffix[i]` for GCD and LCM\n3. update the max **factor score** at the same time\n\ntips:\n`gcd(0, k) = k`\n`lcm(1, k) = k`\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public long maxScore(int[] nums) {\n        int n = nums.length;\n        long[] prefixGCD = new long[n];\n        long[] prefixLCM = new long[n];\n        prefixGCD[0] = nums[0];\n        prefixLCM[0] = nums[0];\n\n        // 1. calculate all prefix[i] for GCD and LCM\n        for (int i = 1; i < n; i++)\n        {\n            prefixGCD[i] = gcd(prefixGCD[i - 1], nums[i]);\n            prefixLCM[i] = lcm(prefixLCM[i - 1], nums[i]);\n        }\n        long ret = prefixGCD[n - 1] * prefixLCM[n - 1]; // select all elements\n\n        // 2. go backward to calculate suffix[i] for GCD and LCM\n        // 3. update the max factor score at the same time\n        long suffixGCD = 0;\n        long suffixLCM = 1;\n        for (int i = n - 1; i >= 1; i--)\n        {\n            // remove one element\n            long score = lcm(prefixLCM[i - 1], suffixLCM) * gcd(prefixGCD[i - 1], suffixGCD);\n            ret = Math.max(ret, score);\n\n            suffixGCD = gcd(suffixGCD, nums[i]);\n            suffixLCM = lcm(suffixLCM, nums[i]);\n        }\n        ret = Math.max(ret, suffixGCD * suffixLCM);\n\n        return ret;\n    }\n\n    long gcd(long a, long b)\n    {\n        return b == 0 ? a : gcd(b, a % b);\n    }\n\n    long lcm(long a, long b)\n    {\n        return a * b / gcd(a, b);\n    }\n}\n```
['Java']