Find the maximum sequence value of array

Array Dynamic Programming Bit Manipulation

21.2% acceptance

Feb 25, 2026

You are given an integer array nums and a positive integer k. The value of a sequence seq of size 2*x is defined as: (seq[0] OR seq[1] OR ... OR seq[x-1]) XOR (seq[x] OR seq[x+1] OR ... OR seq[2*x-1]). Return the maximum value of any subsequence of nums having size 2*k.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_value(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    // prefix_dp[i][j][mask] = set of OR values achievable selecting j elements from nums[0..i]
    // We need: for each split point m, max OR(first k from 0..m) XOR OR(last k from m..n)
    
    // dp_left[i][j] = set of OR values achievable picking j elements from nums[0..i]
    // dp_right[i][j] = set of OR values achievable picking j elements from nums[i..n]
    // Since nums[i] < 128, OR values are in 0..127
    
    let bits = 128usize;
    // left[i] = set of achievable OR values picking exactly k elements from nums[0..i]
    // We build incrementally
    // left_set[i] = set of OR values of size-k subsequences ending at or before index i
    
    // dp[j][v] = can we pick exactly j elements from nums[0..i] with OR = v?
    // Use bitset of 128 bits per j
    let mut left = vec![vec![false; bits]; k + 1]; // left[j][v] = achievable
    left[0][0] = true;
    
    // left_reachable[i] = set of achievable k-element OR values from nums[0..=i]
    let mut left_reach: Vec<Vec<bool>> = Vec::with_capacity(n);
    
    for i in 0..n {
      // update in reverse to avoid using same element twice
      for j in (1..=k).rev() {
        for v in 0..bits {
          if left[j-1][v] {
            left[j][v | nums[i] as usize] = true;
          }
        }
      }
      left_reach.push(left[k].clone());
    }
    
    // right[j][v] from right side
    let mut right = vec![vec![false; bits]; k + 1];
    right[0][0] = true;
    
    let mut ans = 0;
    for i in (0..n).rev() {
      // right currently holds achievable values from nums[i+1..n]
      // Check: left_reach[i] XOR right[k]
      if i + 1 <= n - k { // enough elements on right
        for lv in 0..bits {
          if left_reach[i][lv] {
            for rv in 0..bits {
              if right[k][rv] {
                ans = ans.max((lv ^ rv) as i32);
              }
            }
          }
        }
      }
      // Add nums[i] to right side
      for j in (1..=k).rev() {
        for v in 0..bits {
          if right[j-1][v] {
            right[j][v | nums[i] as usize] = true;
          }
        }
      }
    }
    ans
  }
}