Focus on the largest bit
Intuition\n Describe your first thoughts on how to solve this problem. \nDoing *2 is the same as shifting left (<<1). Here, we will focus on the maximum bit (=l
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDoing *2 is the same as shifting left (<<1). Here, we will focus on the maximum bit (=l). To maximize the answer, we need to make at least l as large as possible. If you think about it that way, it turns out that it\'s best to shift a single element k times. This is because if we operate k-1 times on nums[i] and once on nums[j], if we instead operate k times on nums[i], we get l+=1.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\ntypedef long long ll;\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        int n=nums.size();\n        vector<ll>l(n+1),r(n+1);\n        for(int i=0;i<n-1;i++){\n            l[i+1]|=l[i]|nums[i];\n        }\n        for(int i=n-1;i>=1;i--){\n            r[i-1]|=r[i]|nums[i];\n        }\n        ll ans=0;\n        for(int i=0;i<n;i++){\n            ll tmp=l[i]|r[i]|((ll)nums[i]<<k);\n            ans=max(ans,tmp);\n        }\n        return ans;\n    }\n};\n```
['C++']