数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究在 C++ 中最大化数组的按位 OR
问题陈述
给定一个长度为 N 的整数数组。通过执行一项任务，最大化数组中所有元素的按位 OR。任务是用给定的整数 x 将数组中的任意元素乘以最多 k 次
如果输入数组为 {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
更新时间： 2019-12-24
736 次浏览
广告