Greedy and prefix OR
Intuition\n Describe your first thoughts on how to solve this problem. \nYou need to put all k to one element to make sure the lest most 1;\nHowever, the elemen
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nYou need to put all k to one element to make sure the lest most 1;\nHowever, the element is not necessary the largest element, eg:\n[100000001,\n100000010,\n100]\nk = 1,\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\nO(N)\n# Code\n```\nclass Solution {\n    public long maximumOr(int[] nums, int k) {\n        int n = nums.length, pre[] = new int[n], post[] = new int[n];\n        long res = 0L;\n        for (int i = 1; i < n; i++) {\n            // pre[i] is the prefix or for i, nums[0] | ... | nums[i - 1]\n            pre[i] = pre[i - 1] | nums[i - 1]; \n            // post[i] is the suffix or for i, nums[i + 1] | ... | nums[n - 1]\n            post[n - 1 - i] = post[n - 1 - i + 1] | nums[n - 1 - i + 1];\n        }\n        for (int i = 0; i < n; i++) {\n            res = Math.max(res, pre[i] | (long) nums[i] << k | post[i]);\n        }\n        return res;\n    }\n}\n```
['Java']