P3287 - Find the Maximum Sequence Value of Array

Let $L_i$ be a split line that divides the array into two parts, the left part is $A_i:[0,i]$, and the right part is $B_i:[i+1,n-1]$. And that all meet $len(A),len(B)>=k$.

Let $S_{A_i}^k$ is the set of all subsequences of $A_i$ with length $k$; $S_{B_i}^k$ is the set of all subsequences of $B_i$ with length $k$.

We need to find a way to calculate $S_{A_i}^k$ and $S_{B_i}^k$.

We have that $S_{A_i}^k=S_{A_{i-1}}^k\cup \{x\cup \{e_i\}|x\in S_{A_{i-1}}^{k-1}\}$. The same for $S_{B_i}^k$.

Solution

use std::collections::HashSet;

pub fn max_value(nums: Vec<i32>, k: i32) -> i32 {
    fn find_ors(nums: impl Iterator<Item = i32>, k: usize) -> Vec<HashSet<i32>> {
        let mut dp = vec![];
        let mut prev = vec![HashSet::new(); k + 1]; // prev[i] := a set with i elements
        prev[0].insert(0); // prev[i] as guard helper
        for (i, y) in nums.enumerate() {
            let range = (0..=std::cmp::min(k - 1, i + 1)).rev();
            for j in range {
                let (before, after) = prev.split_at_mut(j + 1);
                for &x in before[j].iter() {
                    after[0].insert(x | y);
                }
            }
            dp.push(prev[k].clone());
        }
        dp
    }

    let k = k as usize;
    let a = find_ors(nums.iter().copied(), k);
    let b = find_ors(nums.iter().rev().copied(), k);
    let mut max = 0;
    let range = (k - 1)..(nums.len() - k);
    for i in range {
        for &va in a[i].iter() {
            for &vb in b[nums.len() - i - 2].iter() {
                max = max.max(va ^ vb);
            }
        }
    }

    max
}

Complexity

The time complexity is $O(n\cdot C_n^k)$, and the space complexity is $O(n\cdot C_n^k)$.