brute force --> better --> optimal ||🧮 || find maximal factor score of array ||
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    brute force -- O(N^2)\n    optimal -- O(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(1)\n\n# Code\n```java []\nclass Solution {\n    public long computeGCD(long x, long y) {\n        if (y == 0) return x;\n        return computeGCD(y, x % y);\n    }\n\n    public long computeLCM(long x, long y) {\n        return (x * y) / computeGCD(x, y);\n    }\n\n    public long maxScore(int[] numbers) {\n        long overallGCD = 0;\n        long overallLCM = 1;\n\n        for (int number : numbers) {\n            overallGCD = computeGCD(overallGCD, number);\n            overallLCM = computeLCM(overallLCM, number);\n        }\n\n        long highestFactorScore = overallGCD * overallLCM;\n\n        for (int i = 0; i < numbers.length; i++) {\n            long currentGCD = 0;\n            long currentLCM = 1;\n\n            for (int j = 0; j < numbers.length; j++) {\n                if (i != j) {\n                    currentGCD = computeGCD(currentGCD, numbers[j]);\n                    currentLCM = computeLCM(currentLCM, numbers[j]);\n                }\n            }\n\n            highestFactorScore = Math.max(highestFactorScore, currentGCD * currentLCM);\n        }\n\n        return highestFactorScore;\n    }\n}\n```\n```java []\nclass Solution {\n    public long maxScore(int[] numbers) {\n        int length = numbers.length; \n        if (length == 1) return (long) numbers[0] * numbers[0];\n        \n        int[] prefixGCD = new int[length];\n        int[] suffixGCD = new int[length];\n        long[] prefixLCM = new long[length], suffixLCM = new long[length];\n\n        prefixGCD[0] = numbers[0];\n        suffixGCD[length - 1] = numbers[length - 1];\n        prefixLCM[0] = numbers[0];\n        suffixLCM[length - 1] = numbers[length - 1];\n\n        for (int i = 1; i < length; i++) {\n            prefixGCD[i] = computeGCD(prefixGCD[i - 1], numbers[i]);\n            prefixLCM[i] = computeLCM(prefixLCM[i - 1], numbers[i]);\n        }\n\n        for (int i = length - 2; i >= 0; i--) {\n            suffixGCD[i] = computeGCD(suffixGCD[i + 1], numbers[i]);\n            suffixLCM[i] = computeLCM(suffixLCM[i + 1], numbers[i]);\n        }\n        \n        long maxScore = (long) prefixGCD[length - 1] * prefixLCM[length - 1];\n        \n        for (int i = 0; i < length; i++) {\n            int currentGCD, currentLCM;\n            if (i == 0) {\n                currentGCD = suffixGCD[1];\n                currentLCM = (int) suffixLCM[1];\n            } else if (i == length - 1) {\n                currentGCD = prefixGCD[length - 2];\n                currentLCM = (int) prefixLCM[length - 2];\n            } else {\n                currentGCD = computeGCD(prefixGCD[i - 1], suffixGCD[i + 1]);\n                currentLCM = (int) computeLCM(prefixLCM[i - 1], suffixLCM[i + 1]);\n            }\n            maxScore = Math.max(maxScore, (long) currentGCD * currentLCM);\n        }\n        return maxScore;\n    }\n\n    private long computeLCM(long a, long b) {\n        return (a / computeGCD(a, b)) * b;\n    }\n\n    private int computeGCD(long a, long b) {\n        while (b != 0) {\n            long temp = a % b;\n            a = b;\n            b = temp;\n        }\n        return (int) a;\n    }\n}\n\n```
['Array', 'Math', 'Suffix Array', 'Number Theory', 'Prefix Sum', 'Java']