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^k_{A_i}$ is the set of all subsequences of $A_i$ with length $k$; $S^k_{B_i}$ is the set of all subsequences of $B_i$ with length $k$.

We need to find a way to calculate $S^k_{A_i}$ and $S^k_{B_i}$.

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

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^k_n)$, and the space complexity is $O(n \cdot C^k_n)$.