登录
求出数组中最大序列值
2025年1月3日 09:21
方法一：动态规划
思路
长度为 $2k$ 的序列的值的计算方式为，先将其拆成长度相同的前后子串，然后分别计算各子串的所有元素的按位或的结果，再将两个按位或的结果进行按位异或。为了求出 $\textit{nums}$ 的长度为 $2k$ 的子序列的最大值，可以将 $\textit{nums}$ 分成左右两半，分别求出每一半中，长度为 $k$ 的子序列的按位或的所有可能性，再两两求异或的最大值。这样的分法一共有 $n-2k+1$ 种，其中 $n$ 为数组 $\textit{nums}$ 的长度。并且我们可以用动态规划的方法来求出长度为 $k$ 的子序列的按位或的结果的所有可能性。
记 $\textit{dp}[i][j]$ 为哈希集合，表示 $\textit{nums}[0...i]$ 中长度为 $j$ 的自序列按位或的所有可能性。$j \leq k$，且当 $j$ 为 $0$ 时，$\textit{dp}[i][j]$ 为空集。又根据题目限制，$\textit{nums}$ 元素的值为 $0$ 到 $127$，因此 $\textit{dp}[i][j]$ 最多包含 $128$ 个元素。进行转移时，$\textit{dp}[i][j]$ 首先会包含 $\textit{dp}[i-1][j]$ 的所有元素，表示不选取 $\textit{nums}[i]$。还可以将 $\textit{dp}[i-1][j-1]$ 中的所有元素与 $\textit{nums}[i]$ 进行按位或，将结果添加进 $\textit{dp}[i][j]$，表示选取$\textit{nums}[i]$。我们可以将上述步骤抽象成一个函数，并进一步降低空间复杂度，只返回值 $j=k$ 时的 $dp$值，可以算出左一半的长度为 $k$ 的子序列的按位或的所有可能性。再将 $\textit{nums}$ 进行逆序后再次应用这个函数，即可计算出右一半的的长度为 $k$ 的子序列的按位或的所有可能性。再两两求异或的最大值返回。
我们可以将
代码
###Python
class Solution:
def maxValue(self, nums: List[int], k: int) -> int:
def findORs(nums: List[int], k: int) -> List[set[int]]:
dp = []
prev = [set() for _ in range(k + 1)]
prev[0].add(0)
for i, num in enumerate(nums):
for j in range(min(k - 1, i + 1), -1, -1):
for x in prev[j]:
prev[j + 1].add(x | num)
dp.append(prev[k].copy())
return dp
A = findORs(nums, k)
B = findORs(nums[::-1], k)
mx = 0
for i in range(k - 1, len(nums) - k):
mx = max(mx, *(a ^ b for a in A[i] for b in B[-i - 2]))
return mx
###Java
class Solution {
public int maxValue(int[] nums, int k) {
List<Set<Integer>> A = findORs(nums, k);
List<Set<Integer>> B = findORs(reverse(nums), k);
int mx = 0;
for (int i = k - 1; i < nums.length - k; i++) {
for (int a : A.get(i)) {
for (int b : B.get(nums.length - i - 2)) {
mx = Math.max(mx, a ^ b);
}
}
}
return mx;
}
private List<Set<Integer>> findORs(int[] nums, int k) {
List<Set<Integer>> dp = new ArrayList<>();
List<Set<Integer>> prev = new ArrayList<>();
for (int i = 0; i <= k; i++) {
prev.add(new HashSet<>());
}
prev.get(0).add(0);
for (int i = 0; i < nums.length; i++) {
for (int j = Math.min(k - 1, i + 1); j >= 0; j--) {
for (int x : prev.get(j)) {
prev.get(j + 1).add(x | nums[i]);
}
}
dp.add(new HashSet<>(prev.get(k)));
}
return dp;
}
private int[] reverse(int[] nums) {
int[] reversed = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
reversed[i] = nums[nums.length - 1 - i];
}
return reversed;
}
}
###C#
public class Solution {
public int MaxValue(int[] nums, int k) {
var A = FindORs(nums, k);
Array.Reverse(nums);
var B = FindORs(nums, k);
int mx = 0;
for (int i = k - 1; i < nums.Length - k; i++) {
foreach (int a in A[i]) {
foreach (int b in B[nums.Length - i - 2]) {
mx = Math.Max(mx, a ^ b);
}
}
}
return mx;
}
public List<HashSet<int>> FindORs(int[] nums, int k) {
var dp = new List<HashSet<int>>();
var prev = new List<HashSet<int>>();
for (int i = 0; i <= k; i++) {
prev.Add(new HashSet<int>());
}
prev[0].Add(0);
for (int i = 0; i < nums.Length; i++) {
for (int j = Math.Min(k - 1, i + 1); j >= 0; j--) {
foreach (int x in prev[j]) {
prev[j + 1].Add(x | nums[i]);
}
}
dp.Add(new HashSet<int>(prev[k]));
}
return dp;
}
}
###C++
class Solution {
public:
int maxValue(vector<int>& nums, int k) {
auto findORs = [&](const vector<int>& nums, int k) -> vector<unordered_set<int>> {
vector<unordered_set<int>> dp;
vector<unordered_set<int>> prev(k + 1);
prev[0].insert(0);
for (int i = 0; i < nums.size(); ++i) {
for (int j = min(k - 1, i + 1); j >= 0; --j) {
for (int x : prev[j]) {
prev[j + 1].insert(x | nums[i]);
}
}
dp.push_back(prev[k]);
}
return dp;
};
vector<unordered_set<int>> A = findORs(nums, k);
vector<unordered_set<int>> B = findORs(vector<int>(nums.rbegin(), nums.rend()), k);
int mx = 0;
for (size_t i = k - 1; i < nums.size() - k; ++i) {
for (int a : A[i]) {
for (int b : B[nums.size() - i - 2]) {
mx = max(mx, a ^ b);
}
}
}
return mx;
}
};
###Go
func maxValue(nums []int, k int) int {
findORs := func(nums []int, k int) []map[int]bool {
dp := make([]map[int]bool, 0)
prev := make([]map[int]bool, k + 1)
for i := 0; i <= k; i++ {
prev[i] = make(map[int]bool)
}
prev[0][0] = true
for i := 0; i < len(nums); i++ {
for j := min(k - 1, i + 1); j >= 0; j-- {
for x := range prev[j] {
prev[j + 1][x | nums[i]] = true
}
}
current := make(map[int]bool)
for key := range prev[k] {
current[key] = true
}
dp = append(dp, current)
}
return dp
}
A := findORs(nums, k)
reverse(nums)
B := findORs(nums, k)
mx := 0
for i := k - 1; i < len(nums) - k; i++ {
for a := range A[i] {
for b := range B[len(nums) - i - 2] {
if a ^ b > mx {
mx = a ^ b
}
}
}
}
return mx
}
func reverse(nums []int) {
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
###C
typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
HashItem *hashFindItem(HashItem **obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
return pEntry;
}
bool hashAddItem(HashItem **obj, int key) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
HASH_ADD_INT(*obj, key, pEntry);
return true;
}
void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
void findORs(int* nums, int numsSize, int k, HashItem** dp) {
HashItem *prev[k + 1];
for (int i = 0; i <= k; i++) {
prev[i] = NULL;
}
hashAddItem(&prev[0], 0);
for (int i = 0; i < numsSize; ++i) {
for (int j = fmin(k - 1, i + 1); j >= 0; --j) {
for (HashItem *pEntry = prev[j]; pEntry; pEntry = pEntry->hh.next) {
int x = pEntry->key;
hashAddItem(&prev[j + 1], x | nums[i]);
}
}
for (HashItem *pEntry = prev[k]; pEntry; pEntry = pEntry->hh.next) {
int x = pEntry->key;
hashAddItem(&dp[i], x);
}
}
for (int i = 0; i <= k; i++) {
hashFree(&prev[i]);
}
};
void reverse(int *nums, int numsSize) {
for (int i = 0, j = numsSize - 1; i < j; i++, j--) {
int x = nums[i];
nums[i] = nums[j];
nums[j] = x;
}
}
int maxValue(int* nums, int numsSize, int k) {
HashItem *A[numsSize];
HashItem *B[numsSize];
for (int i = 0; i < numsSize; i++) {
A[i] = B[i] = NULL;
}
findORs(nums, numsSize, k, A);
reverse(nums, numsSize);
findORs(nums, numsSize, k, B);
int mx = 0;
for (size_t i = k - 1; i < numsSize - k; ++i) {
for (HashItem *pEntry = A[i]; pEntry; pEntry = pEntry->hh.next) {
int a = pEntry->key;
for (HashItem *pEntry = B[numsSize - i - 2]; pEntry; pEntry = pEntry->hh.next) {
int b = pEntry->key;
mx = fmax(mx, a ^ b);
}
}
}
for (int i = 0; i < numsSize; i++) {
hashFree(&A[i]);
hashFree(&B[i]);
}
return mx;
}
###JavaScript
var maxValue = function(nums, k) {
function findORs(nums, k) {
const dp = [];
const prev = Array.from({ length: k + 1 }, () => new Set());
prev[0].add(0);
for (let i = 0; i < nums.length; i++) {
for (let j = Math.min(k - 1, i + 1); j >= 0; j--) {
for (const x of prev[j]) {
prev[j + 1].add(x | nums[i]);
}
}
dp.push(new Set(prev[k]));
}
return dp;
}
const A = findORs(nums, k);
nums.reverse();
const B = findORs(nums, k);
let mx = 0;
for (let i = k - 1; i < nums.length - k; i++) {
for (const a of A[i]) {
for (const b of B[nums.length - i - 2]) {
mx = Math.max(mx, a ^ b);
}
}
}
return mx;
};
###TypeScript
function maxValue(nums: number[], k: number): number {
function findORs(nums: number[], k: number): Set<number>[] {
const dp: Set<number>[] = [];
const prev: Set<number>[] = Array.from({ length: k + 1 }, () => new Set());
prev[0].add(0);
for (let i = 0; i < nums.length; i++) {
for (let j = Math.min(k - 1, i + 1); j >= 0; j--) {
for (const x of prev[j]) {
prev[j + 1].add(x | nums[i]);
}
}
dp.push(new Set(prev[k]));
}
return dp;
}
const A = findORs(nums, k);
nums.reverse();
const B = findORs(nums, k);
let mx = 0;
for (let i = k - 1; i < nums.length - k; i++) {
for (const a of A[i]) {
for (const b of B[nums.length - i - 2]) {
mx = Math.max(mx, a ^ b);
}
}
}
return mx;
};
###Rust
use std::collections::HashSet;
use std::cmp::{max, min};
impl Solution {
pub fn max_value(nums: Vec<i32>, k: i32) -> i32 {
fn find_ors(nums: &Vec<i32>, k: i32) -> Vec<HashSet<i32>> {
let mut dp = Vec::new();
let mut prev = vec![HashSet::new(); k as usize + 1];
prev[0].insert(0);
for i in 0..nums.len() {
for j in (0..= min(k as usize - 1, i + 1)).rev() {
let (before, after) = prev.split_at_mut(j + 1);
for &x in &before[j] {
after[0].insert(x | nums[i]);
}
}
dp.push(prev[k as usize].clone());
}
dp
}
let a = find_ors(&nums, k);
let reversed_nums: Vec<i32> = nums.iter().rev().cloned().collect();
let b = find_ors(&reversed_nums, k);
let mut mx = 0;
for i in k as usize - 1..nums.len() - k as usize {
for &a_val in &a[i] {
for &b_val in &b[nums.len() - i - 2] {
mx = mx.max(a_val ^ b_val);
}
}
}
mx
}
}
复杂度分析
-
时间复杂度：$O(n \times k \times U + n \times U^2)$，其中 $n$ 是数组 $\textit{nums}$ 的长度，$U$ 是数组元素的可能性集合大小。$\textit{dp}$ 的状态有 $O(n\times k)$ 种，每个状态消耗 $O(U)$ 计算。最后两两求异或消耗 $O(n\times U^2)$ 的时间。
-
空间复杂度：$O(n \times U)$。
{:width=400}