Prefix and suffix array in python.
Approach\nFor every num in the nums array, we will multiply num by 2^k, and keep a track of the bitwise OR of all the array elements taken together. To perform 
# Approach\nFor every num in the nums array, we will multiply num by 2^k, and keep a track of the bitwise OR of all the array elements taken together. To perform this computation optimally, we keep a prefix and a suffix array.\n    `prefix[i] = bitwise OR of elements at index 0 to i-1.`\n    `suffix[i] = bitwise OR of elements at index i+1 to n-1.`\n\nThe reason why we are multiplying a single element by 2^k instead of multiple elements is simple. If we spread out the k over multiple elements, our max OR will not be multiplied by the most optimal multiplicative factor that it could have been.  \n\n# Complexity\n- Time complexity: O(N)\n\n- Space complexity: O(N)\n\n# Code\n```\nclass Solution:\n    def maximumOr(self, nums: List[int], k: int) -> int:        \n        pre = [0]\n        or_val = 0\n        for num in nums:\n            or_val |= num\n            pre.append(or_val)\n        pre.pop()\n\n        suf = [0]\n        or_val = 0\n        for idx in range(len(nums) - 1, -1, -1):\n            num = nums[idx]\n            or_val |= num\n            suf.append(or_val)\n        suf.pop()\n        suf.reverse()\n\n        max_or = 0\n        for idx in range(len(nums)):\n            num = nums[idx] << k\n            prefix = pre[idx]\n            suffix = suf[idx]\n\n            max_or = max(max_or, num | prefix | suffix)\n\n        return (max_or)\n\n```
['Greedy', 'Suffix Array', 'Prefix Sum', 'Python', 'Python3']