Step-by-Step Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nYou\u2019re given a list of numbers, and your mission (should you choose to accept it
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nYou\u2019re given a list of numbers, and your mission (should you choose to accept it) is to calculate the maximum score by playing around with the GCD (Greatest Common Divisor) and LCM (Least Common Multiple) of these numbers.\n\nSo, imagine you\u2019re handed a few numbers on a piece of paper. Your goal is to create the highest score possible by performing some clever calculations. What you\u2019re going to do is:\n\n1. For every number, calculate the GCD and LCM in a way that considers that number and all the numbers after it in the list.\n2. Find the combination that gives you the maximum value when you multiply the LCM and GCD of a sub-list.\n3. And voil\xE0, that\u2019s your answer!\n\nThe code tries to perform these calculations efficiently, because who wants to spend too long crunching numbers?\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. Helper Functions:\n    - gcd(a, b): This function calculates the greatest common divisor using recursion.\n    - lcm(a, b): This function calculates the least common multiple using the GCD function.\n\n2. Calculate GCD and LCM Arrays:\n    - We start by creating two vectors (gcdNums and lcmNums) to store the cumulative GCD and LCM from each index to the end.\n    - We fill gcdNums and lcmNums starting from the end of the nums list.\n\n3. Maximizing the Score:\n\n    - We initialize a result res using the product of the full list\'s LCM and GCD from the first element.\n    - We then iterate through the list:\n        - At each index, we try removing the element at that position and calculate the LCM and GCD of the remaining elements.\n        - If the calculated product is higher than res, we update res.\n    - Finally, we return the maximum score found.\n\n# Step-by-Step\n\nImagine your list as a series of elements:\n\n- Start with calculating the GCD and LCM arrays, filling them from the end to the start:\n\n```ruby []\nnums:    [a, b, c, d, e]\ngcdNums: [GCD(a, b, c, d, e), GCD(b, c, d, e), ..., GCD(e)]\nlcmNums: [LCM(a, b, c, d, e), LCM(b, c, d, e), ..., LCM(e)]\n```\n\n- For each element i in nums, calculate the maximum possible res by removing element i and taking the product of the GCD and LCM of the remaining elements. For example:\n\n```ruby []\nRemove a:\n     GCD(b, c, d, e) * LCM(b, c, d, e)\n```\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nThe overall time complexity is \n`\uD835\uDC42(\uD835\uDC5B)`\nwhere n is the length of nums. Calculating GCD and LCM for each pair takes constant time (in practice), and filling up gcdNums and lcmNums takes linear time since we only calculate each once.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nWe\u2019re using additional arrays gcdNums and lcmNums of size \n`\uD835\uDC42(\uD835\uDC5B)` to store cumulative values. So, the space complexity is \n`\uD835\uDC42(\uD835\uDC5B)`.\n\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long gcd(long long a, long long b) {\n        if(b == 0) return a;\n        return gcd(b, a % b);\n    }\n\n    long long lcm(long long a, long long b) {\n        return (a / gcd(a, b)) * b;\n    }\n\n    long long maxScore(vector<int>& nums) {\n        int n = nums.size();\n        vector<long long> gcdNums(n), lcmNums(n);\n        gcdNums[n - 1] = nums[n - 1];\n        lcmNums[n - 1] = nums[n - 1];\n        for(int i = n - 2; i >= 0; i--) {\n            lcmNums[i] = lcm(nums[i], lcmNums[i + 1]);\n            gcdNums[i] = gcd(nums[i], gcdNums[i + 1]);\n        }\n        long long res = lcmNums[0] * gcdNums[0];\n        long long cLcm = nums[0], cGcd = nums[0];\n        for(int i = 0; i < n - 1; ++i) {\n            // remove the element\n            if(i == 0) res = max(res, lcmNums[i + 1] * gcdNums[i + 1]);\n            else res = max(res, lcm(cLcm, lcmNums[i + 1]) * gcd(cGcd, gcdNums[i + 1]));\n            cLcm = lcm(cLcm, nums[i]);\n            cGcd = gcd(cGcd, nums[i]);\n        }\n        res = max(res, cLcm * cGcd);\n        return res;\n    }\n};\n```
['C++']