資料結構
網路
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 次瀏覽
廣告