最大化C ++中数组的按位或
问题陈述
给定一个由N个整数组成的数组。必须通过执行一项任务来最大化数组所有元素的按位或。任务是将数组的任何元素最多k次与给定的整数x相乘
如果输入数组为{4，3，6，1}，k=2且x=3，则可获得的最大值为55
算法
1. multiply an array element with (x^k) and do bitwise OR it with the bitwise OR of all previous elements 2. Multiply an array element with bitwise OR of all next elements 3. Return the maximum value after all iterations
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxOr(int *arr, int n, int k, int x){
int prefixSum[n + 1];
int suffixSum[n + 1];
int power = 1;
for (int i = 0; i < k; ++i) {
power = power * x;
}
prefixSum[0] = 0;
for (int i = 0; i < n; ++i) {
prefixSum[i + 1] = prefixSum[i] | arr[i];
}
suffixSum[n] = 0;
for (int i = n - 1; i >= 0; --i) {
suffixSum[i] = suffixSum[i + 1] | arr[i];
}
int result = INT_MIN;
for (int i = 0; i < n; ++i) {
result = max(result, prefixSum[i] | (arr[i] * power) | suffixSum[i + 1]);
}
return result;
}
int main(){
int arr[] = {4, 3, 6, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
int x = 3;
cout << "Result = " << getMaxOr(arr, n, k, x) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它生成以下输出-
Result = 55
热门推荐
10 朋友新年祝福语大全 简短
11 新年祝福语简短大方兔年
12 搬新家礼物祝福语简短
13 同学见面花束祝福语简短
14 五一假期祝福语幽默简短
15 离职欢送敬酒祝福语简短
16 对学弟的祝福语简短
17 考老师辞职祝福语简短
18 祝福语驱散霉运的话简短