WA on new testcases | Try All Ways | Bottom Up & Top Down DP | Try all ways | C++ | Java
Idea:\nKnapSack -> Pick or not pick\nPick, how many times we can multiply current number by 2, then do OR\nSkip, just do OR and move to next\n\nC++\nTop Down\n\
**Idea:**\nKnapSack -> Pick or not pick\nPick, how many times we can multiply current number by 2, then do `OR`\nSkip, just do `OR` and move to next\n\nC++\n**Top Down**\n```\n// TC: O(N * K * K)\n// SC: O(N * K)\n#define ll long long\nclass Solution {\n    ll memo[100001][16];\n\n    ll rec(vector<int> &arr, int i, int k){\n        if(i == arr.size()) return 0;\n        if(memo[i][k] !=- 1) return memo[i][k];\n        \n        ll maxi = arr[i] | rec(arr, i + 1, k);;\n        \n        for(ll j = 1; j <= k; j++){\n            ll value = arr[i];        \n            ll cur = (value << j); // it equals to value * pow(2, j)\n                \n            maxi = max(maxi, cur | rec(arr, i + 1, k - j));\n        }\n        return memo[i][k] = maxi;\n    }\npublic:\n    long long maximumOr(vector<int>& arr, int k){\n        memset(memo, -1, sizeof(memo));\n        return rec(arr, 0, k);\n    }\n};\n```\n**Bottom Up**\n```\n#define ll long long\nclass Solution {\npublic:\n    long long maximumOr(vector<int>& arr, int k){\n        int n = arr.size();\n        ll dp[n + 1][k + 1];\n        \n        for(int i = n; i >= 0; i--){\n            for(int j = 0; j < k + 1; j++){\n                if(i == n){\n                    dp[i][j] = 0;\n                    continue;\n                }\n                \n                ll maxi = arr[i] | dp[i + 1][j];\n        \n                for(ll l = 1; l <= j; l++){\n                    ll value = arr[i];        \n                    ll cur = (value << l);\n\n                    maxi = max(maxi, cur | dp[i + 1][j - l]);\n                }\n                dp[i][j] = maxi;\n            }\n        }\n        return dp[0][k];\n    }\n};\n```\n**Java**\n```\nclass Solution {\n    public long maximumOr(int[] nums, int k) {\n        long[][] memo = new long[nums.length][k + 1];\n        for (int i = 0; i < nums.length; i++) {\n            Arrays.fill(memo[i], -1);\n        }\n        return rec(nums, 0, k, memo);\n    }\n    \n    private long rec(int[] nums, int i, int k, long[][] memo) {\n        if (i == nums.length) {\n            return 0;\n        }\n        if (memo[i][k] != -1) {\n            return memo[i][k];\n        }\n        \n        long maxi = nums[i] | rec(nums, i + 1, k, memo);\n        \n        for (int j = 1; j <= k; j++) {\n            long value = nums[i];\n            long cur = (value << j);\n            maxi = Math.max(maxi, cur | rec(nums, i + 1, k - j, memo));\n        }\n        memo[i][k] = maxi;\n        return maxi;\n    }\n}\n```
['Dynamic Programming']