Skip to main content
Back to problems
#2172
Hard Algorithms

Maximum and sum of array

Array Dynamic Programming Bit Manipulation Bitmask
50.7% acceptance
Feb 25, 2026
549
33
You are given an integer array nums and an integer numSlots such that 2 * numSlots >= n. Place all n integers into numSlots slots (each slot holds at most 2 numbers). The AND sum = sum of (num AND slot_number) for each placement. Return the maximum possible AND sum.

Solution

Rust
Time O(n³)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn maximum_and_sum(nums: Vec<i32>, num_slots: i32) -> i32 {
    let ns = num_slots as usize;
    let total = 1usize << (2 * ns); // 2 bits per slot
    let mut dp = vec![0i32; total];
    let n = nums.len();

    for mask in 0..total {
      let cnt = (mask as u32).count_ones() as usize;
      if cnt >= n {
        continue;
      }
      let num = nums[cnt];
      for slot in 0..ns {
        let slot_num = (slot + 1) as i32;
        for bit_offset in 0..2usize {
          let bit = 2 * slot + bit_offset;
          if mask & (1 << bit) == 0 {
            let new_mask = mask | (1 << bit);
            dp[new_mask] = dp[new_mask].max(dp[mask] + (num & slot_num));
          }
        }
      }
    }

    *dp.iter().max().unwrap()
  }
}