Hard
题目描述
给你一个整数数组 nums 和一个正整数 k。
大小为 2 * x 的序列 seq 的值定义为：
(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1])
返回 nums 中任意大小为 2 * k 的子序列的最大值。
示例 1：
输入：nums = [2,6,7], k = 1
输出：5
解释：子序列 [2, 7] 的最大值为 2 XOR 7 = 5。
示例 2：
输入：nums = [4,2,5,6,7], k = 2
输出：2
解释：子序列 [4, 5, 6, 7] 的最大值为 (4 OR 5) XOR (6 OR 7) = 2。
约束条件：
2 <= nums.length <= 4001 <= nums[i] < 2^71 <= k <= nums.length / 2
解题思路
这道题需要我们找到一个长度为 2*k 的子序列，使得前 k 个元素的OR值与后 k 个元素的OR值的XOR结果最大。
关键思路是使用动态规划：
预处理阶段：对于每个位置，计算从左边选择不同数量元素时所有可能的OR值，以及从右边选择不同数量元素时所有可能的OR值。
状态定义：
leftDP[i][j]表示从前i个元素中选择j个元素的所有可能OR值的集合rightDP[i][j]表示从后n-i个元素中选择j个元素的所有可能OR值的集合
转移方程：
- 对于左侧：
leftDP[i][j] = leftDP[i-1][j] ∪ {x | nums[i-1] for x in leftDP[i-1][j-1]} - 对于右侧：类似处理
- 对于左侧：
答案计算：枚举分割点，左边选择
k个元素，右边选择k个元素，计算所有可能的XOR值的最大值。
由于数值范围小于 2^7 = 128，我们可以用集合或布尔数组来存储所有可能的OR值，这样可以有效控制状态空间。
代码实现
class Solution {
public:
int maxValue(vector<int>& nums, int k) {
int n = nums.size();
// leftDP[i][j] 表示从前i个元素中选j个的所有可能OR值
vector<vector<vector<bool>>> leftDP(n + 1, vector<vector<bool>>(k + 1, vector<bool>(128, false)));
// rightDP[i][j] 表示从后n-i个元素中选j个的所有可能OR值
vector<vector<vector<bool>>> rightDP(n + 1, vector<vector<bool>>(k + 1, vector<bool>(128, false)));
leftDP[0][0][0] = true;
rightDP[n][0][0] = true;
// 计算左侧DP
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= min(i, k); j++) {
// 不选第i个元素
for (int val = 0; val < 128; val++) {
leftDP[i][j][val] = leftDP[i-1][j][val];
}
// 选第i个元素
if (j > 0) {
for (int val = 0; val < 128; val++) {
if (leftDP[i-1][j-1][val]) {
leftDP[i][j][val | nums[i-1]] = true;
}
}
}
}
}
// 计算右侧DP
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= min(n - i, k); j++) {
// 不选第i+1个元素
for (int val = 0; val < 128; val++) {
rightDP[i][j][val] = rightDP[i+1][j][val];
}
// 选第i+1个元素
if (j > 0) {
for (int val = 0; val < 128; val++) {
if (rightDP[i+1][j-1][val]) {
rightDP[i][j][val | nums[i]] = true;
}
}
}
}
}
int maxVal = 0;
// 枚举分割点
for (int i = k; i <= n - k; i++) {
for (int left = 0; left < 128; left++) {
if (leftDP[i][k][left]) {
for (int right = 0; right < 128; right++) {
if (rightDP[i][k][right]) {
maxVal = max(maxVal, left ^ right);
}
}
}
}
}
return maxVal;
}
};
class Solution:
def maxValue(self, nums: List[int], k: int) -> int:
n = len(nums)
# leftDP[i][j] 表示从前i个元素中选j个的所有可能OR值
leftDP = [[[False] * 128 for _ in range(k + 1)] for _ in range(n + 1)]
# rightDP[i][j] 表示从后n-i个元素中选j个的所有可能OR值
rightDP = [[[False] * 128 for _ in range(k + 1)] for _ in range(n + 1)]
leftDP[0][0][0] = True
rightDP[n][0][0] = True
# 计算左侧DP
for i in range(1, n + 1):
for j in range(min(i, k) + 1):
# 不选第i个元素
for val in range(128):
leftDP[i][j][val] = leftDP[i-1][j][val]
# 选第i个元素
if j > 0:
for val in range(128):
if leftDP[i-1][j-1][val]:
leftDP[i][j][val | nums[i-1]] = True
# 计算右侧DP
for i in range(n - 1, -1, -1):
for j in range(min(n - i, k) + 1):
# 不选第i+1个元素
for val in range(128):
rightDP[i][j][val] = rightDP[i+1][j][val]
# 选第i+1个元素
if j > 0:
for val in range(128):
if rightDP[i+1][j-1][val]:
rightDP[i][j][val | nums[i]] = True
maxVal = 0
# 枚举分割点
for i in range(k, n - k + 1):
for left in range(128):
if leftDP[i][k][left]:
for right in range(128):
if rightDP[i][k][right]:
maxVal = max(maxVal, left ^ right)
return maxVal
public class Solution {
public int MaxValue(int[] nums, int k) {
int n = nums.Length;
// leftDP[i][j] 表示从前i个元素中选j个的所有可能OR值
bool[,,] leftDP = new bool[n + 1, k + 1, 128];
// rightDP[i][j] 表示从后n-i个元素中选j个的所有可能OR值
bool[,,] rightDP = new bool[n + 1, k + 1, 128];
leftDP[0, 0, 0] = true;
rightDP[n, 0, 0] = true;
// 计算左侧DP
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= Math.Min(i, k); j++) {
// 不选第i个元素
for (int val = 0; val < 128; val++) {
leftDP[i, j, val] = leftDP[i-1, j, val];
}
// 选第i个元素
if (j > 0) {
for (int val = 0; val < 128; val++) {
if (leftDP[i-1, j-1, val]) {
leftDP[i, j, val | nums[i-1]] = true;
}
}
}
}
}
// 计算右侧DP
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= Math.Min(n - i, k); j++) {
// 不选第i+1个元素
for (int val = 0; val < 128; val++) {
rightDP[i, j, val] = rightDP[i+1, j, val];
}
// 选第i+1个元素
if (j > 0) {
for (int val = 0; val < 128; val++) {
if (rightDP[i+1, j-1, val]) {
rightDP[i, j, val | nums[i]] = true;
}
}
}
}
}
int maxVal = 0;
// 枚举分割点
for (int i = k; i <= n - k; i++) {
for (int left = 0; left < 128; left++) {
if (leftDP[i, k, left]) {
for (int right = 0; right < 128; right++) {
if (rightDP[i, k, right]) {
maxVal = Math.Max(maxVal, left ^ right);
}
}
}
}
}
return maxVal;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxValue = function(nums, k) {
const n = nums.length;
// leftDP[i][j] 表示从前i个元素中选j个的所有可能OR值
const leftDP = Array.from({length: n + 1}, () =>
Array.from({length: k + 1}, () => new Array(128).fill(false))
);
// rightDP[i][j] 表示从后n-i个元素中选j个的所有可能OR值
const rightDP = Array.from({length: n + 1}, () =>
Array.from({length: k + 1}, () => new Array(128).fill(false))
);
leftDP[0][0][0] = true;
rightDP[n][0][0] = true;
// 计算左侧DP
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= Math.min(i, k); j++) {
// 不选第i个元素
for (let val = 0; val < 128; val++) {
leftDP[i][j][val] = leftDP[i-1][j][val];
}
// 选第i个元素
if (j > 0) {
for (let val = 0; val < 128; val++) {
if (leftDP[i-1][j-1][val]) {
leftDP[i][j][val | nums[i-1]] = true;
}
}
}
}
}
// 计算右侧DP
for (let i = n - 1; i >= 0; i--) {
for (let j = 0; j <= Math.min(n - i, k); j++) {
// 不选第i+1个元素
for (let val = 0; val < 128; val++) {
rightDP[i][j][val] = rightDP[i+1][j][val];
}
// 选第i+1个元素
if (j > 0) {
for (let val = 0; val < 128; val++) {
if (rightDP[i+1][j-1][val]) {
rightDP[i][j][val | nums[i]] = true;
}
}
}
}
}
let maxVal = 0;
// 枚举分割点
for (let i = k; i <= n - k; i++) {
for (let left = 0; left < 128; left++) {
if (leftDP[i][k][left]) {
for (let right = 0; right < 128; right++) {
if (rightDP[i][k][right]) {
maxVal = Math.max(maxVal, left ^ right);
}
}
}
}
}
return maxVal;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n² × k × V) |
| 空间复杂度 | O(n × k × V) |
其中 n 是数组长度，k 是参数，V = 128 是可能的OR值范围。
相关题目
- . Bitwise ORs of Subarrays (Medium)