问题背景
给你一个下标从 0 0 0 开始长度为 n n n 的整数数组 n u m s nums nums 和一个整数 k k k。每一次操作中，你可以选择一个数并将它乘 2 2 2。
你最多可以进行 k k k 次操作，请你返回 n u m s [ 0 ] ∣ n u m s [ 1 ] ∣ . . . ∣ n u m s [ n − 1 ] nums[0] | nums[1] | ... | nums[n - 1] nums[0]∣nums[1]∣...∣nums[n−1] 的最大值。
a ∣ b a | b a∣b 表示两个整数 a a a 和 b b b 的 按位或 运算。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \le nums.length \le 10 ^ 5 1≤nums.length≤105
- 1 ≤ n u m s [ i ] ≤ 1 0 9 1 \le nums[i] \le 10 ^ 9 1≤nums[i]≤109
- 1 ≤ k ≤ 15 1 \le k \le 15 1≤k≤15
解题过程
要求最终或运算的结果最大，应该尽可能地增加它的二进制长度。
乘 2 2 2 和左移是完全等价的，集中对一个数进行不断地左移要比对多个数分散操作更有可能增加数字的二进制长度。
所以只需要遍历并讨论对每个数字进行操作得到的结果，取最大值即可。
要快速计算某个位置上的或运算结果，除了它本身左移之后的数值，还需要它的前后缀或运算结果。为了快速计算，可以先处理好前后缀的值。
具体实现
class Solution {public long maximumOr(int[] nums, int k) {int n = nums.length;int[] sufOrSum = new int[n];for (int i = n - 2; i >= 0; i--) {sufOrSum[i] = sufOrSum[i + 1] | nums[i + 1];}long res = 0;int preOrSum = 0;for (int i = 0; i < n; i++) {res = Math.max(res, preOrSum | ((long) nums[i] << k) | sufOrSum[i]);preOrSum |= nums[i];}return res;}
}
