Maximizing Array Products with Prefix and Suffix GCD-LCM in C++
Intuition\nThe problem requires maximizing a product involving the GCD and LCM of subarrays. By separating the array into different prefix and suffix segments, 
# Intuition\nThe problem requires maximizing a product involving the **GCD** and **LCM **of subarrays. By separating the array into different **prefix **and **suffix **segments, we can efficiently calculate the maximum possible GCD-LCM product using precomputed arrays.\n\n# Approach\n# 1. Precompute Prefix and Suffix Arrays:\nCompute prefix GCDs (gcd_left) and suffix GCDs (gcd_right) for every index to get the GCD of all elements to the left and right.\nSimilarly, compute prefix LCMs (lcm_left) and suffix LCMs (lcm_right) for all elements.\n\n# 2.  Calculate Maximum Product:\nInitialize the answer by considering products at the edges of the array.\nFor each element, compute the maximum GCD-LCM product by excluding the element at index i and combining the left and right segments.\n\n## 3. Return Result: Return the highest product found.\n\n# Complexity\n- Time complexity:\n O(n) as we only make linear passes through the array to compute prefix and suffix GCDs and LCMs.\n\n- Space complexity:\nO(n), for storing the prefix and suffix arrays (gcd_left, gcd_right, lcm_left, lcm_right).\n\n \n\n# Code\n```cpp []\nclass Solution {\npublic:\n    // Function to calculate LCM of two numbers\n    long long lcm(long a ,long b) {\n        return (a / gcd(a, b)) * b;\n    }\n  \n    long long maxScore(vector<int>& nums) {     \n        int n = nums.size();\n        \n        // Edge case: If there\'s only one element, return its square\n        if (n == 1)\n            return nums[0] * nums[0];\n\n        // Prefix and suffix arrays to store GCDs and LCMs\n        vector<long long> gcd_left(n);\n        vector<long long> gcd_right(n);\n        gcd_left[0] = nums[0];\n\n        // Calculate prefix GCDs\n        for (int i = 1; i < n; i++) {\n            gcd_left[i] = gcd(gcd_left[i - 1], nums[i]);\n        }\n\n        gcd_right[n - 1] = nums[n - 1];\n\n        // Calculate suffix GCDs\n        for (int i = n - 2; i >= 0; i--) {\n            gcd_right[i] = gcd(gcd_right[i + 1], nums[i]);\n        }\n\n        // Prefix and suffix arrays to store LCMs\n        vector<long long> lcm_left(n);\n        vector<long long> lcm_right(n);\n        lcm_left[0] = nums[0];\n\n        // Calculate prefix LCMs\n        for (int i = 1; i < n; i++) {\n            lcm_left[i] = lcm(lcm_left[i - 1], nums[i]);\n        }\n\n        lcm_right[n - 1] = nums[n - 1];\n\n        // Calculate suffix LCMs\n        for (int i = n - 2; i >= 0; i--) {\n            lcm_right[i] = lcm(lcm_right[i + 1], nums[i]);\n        }\n        \n        // Initialize answer with max product from edges\n        long long ans = max({gcd_right[1] * lcm_right[1], lcm_left[n - 2] * gcd_left[n - 2]});\n\n        // Calculate maximum product by checking all subarrays\n        for (int i = 1; i < n - 1; i++) {\n            long long a = gcd(gcd_left[i - 1], gcd_right[i + 1]);\n            long long b = lcm(lcm_left[i - 1], lcm_right[i + 1]);\n            ans = max(ans, a * b);\n        }\n\n        // Check the final possible combination\n        long long res = lcm_left[n - 1] * gcd_left[n - 1];\n        ans = max(ans, res);\n        \n        return ans;\n    }\n};\n\n```
['Suffix Array', 'C++']