O(N^2) and O(N) solutions explained.
Intuition\nPick an index to eliminate (-1 for none) and keep track of best score. In the inner loop d is the current gcd, m is the current lcm. Note that: gcd(0
# Intuition\nPick an index to eliminate (-1 for none) and keep track of best score. In the inner loop `d` is the current **gcd**, `m` is the current **lcm**. Note that: `gcd(0, x) = x` and `lcm(1, x) = x`.\n\nSince N is small (up to 100) the brute force $$O(N^2)$$ solution is very fast. For larger values of N (up to $$10^5$$) is worth using a bit of extra memory to improve time efficiency to $$O(N)$$.\n\nSee the second solution which uses prefix and suffix arrays for **gcd** and **lcm**. To calculate `gcd` without index `i` = `gcd(dpre[i-1], dsuf[i+1])`, rather then looping through the remaining n-1 indexes (and similarly for `lcm`).\n\nEven for the small values tested for this problem the second solution is faster then the first `6ms` versus `55ms`.\n\n\n# Code\n**Solution 1**\nTime complexity: $$O(N^2)$$, Space complexity: $$O(1)$$\n```\ndef maxScore(self, nums: List[int]) -> int:\n    n = len(nums)\n    res = 0\n    for i in range(-1, n):\n        d, m = 0, 1\n        for j in range(n):\n            if j != i:\n                d = gcd(d, nums[j])\n                m = lcm(m, nums[j])\n        res = max(res, d * m)\n    return res\n```\n\n**Solution 2**\nTime complexity: $$O(N)$$, Space complexity: $$O(N)$$\n\n```\ndef maxScore(self, nums: List[int]) -> int:\n    def incremental(index_order):\n        darr, marr = [0] * n, [0] * n\n        d, m = 0, 1\n        for i in index_order:\n            d = gcd(d, nums[i])\n            m = lcm(m, nums[i])\n            darr[i], marr[i] = d, m\n        return darr, marr\n\n    n = len(nums)\n    dpre, mpre = incremental(range(n))\n    dsuf, msuf = incremental(reversed(range(n)))\n    res = dpre[-1] * mpre[-1]\n    for i in range(n):\n        d1, d2 = dpre[i - 1] if i > 0 else 0, dsuf[i + 1] if i + 1 < n else 0\n        m1, m2 = mpre[i - 1] if i > 0 else 1, msuf[i + 1] if i + 1 < n else 1\n        res = max(res, gcd(d1, d2) * lcm(m1, m2))\n    return res\n```
['Python3']