Dynamic programming not working || solution using prefix array
Intuition\n Describe your first thoughts on how to solve this problem. \nThis approach is not working for test case -> 6,9,8 and k = 1\nthe ans should be 31 and
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis approach is not working for test case -> 6,9,8 and k = 1\nthe ans should be 31 and my code is giving 30... \nto get answer we multiply 8 by 2 so array will be [6,9,16]\n\nthe dp code is not taking 9|16 (25) as return value instead it is taking 18|8 (26) which is wrong.\nthis is happening because we are maximising our answer in aur recursive code and it is taking 26 as our final value instead of 25 (which gives us the right answer).\n\n\n# Wrong Code\n```\nclass Solution {\n    \n    long long dp[100009][20];\n\n    /// to calculate the power of 2\n    long long cal(int id){\n        long long val = 1LL;\n        while(id--){\n            val*=(2LL);\n        }\n        return val;\n    }\n    \n    long long rec(vector<int> &arr,int id,int k){\n        if(id>=arr.size())\n            return 0;\n        if(dp[id][k]!=-1)\n            return dp[id][k];\n        long long ans = 0;\n        /// how many times should I multiply arr[id] with 2....\n        for(int i = 0;i<=k;i++){\n            ans = max(ans,(cal(i)*arr[id])|(rec(arr,id+1,k-i)));\n        }\n        \n        return dp[id][k] = ans;\n        \n    }\n    \npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        memset(dp,-1,sizeof(dp));\n        return rec(nums,0,k);\n    }\n};\n```\n\n\n# Correct Code\n```\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& nums, int k) {\n        long long ans = 0;\n        vector<long long> suff(nums.size()+1);\n        long long curr = 0;\n        for(int i=nums.size()-1;i>=0;i--){\n            curr|=nums[i];\n            suff[i] = curr;\n        }\n\n        curr = 0;\n\n        for(int i=0;i<nums.size();i++){\n            long long temp = curr;\n            temp |= (nums[i]*(1LL<<k));\n            ans = max(ans,(temp)|(suff[i+1]));\n            curr |= nums[i];\n        }\n\n        return ans;\n    }\n};\n\n```\n
['Dynamic Programming', 'Recursion', 'C++']