最大化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 教师闺蜜祝福语简短