Skip to content

2172. Maximum AND Sum of Array 👍

  • Time: $O(2^n \cdot n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int maximumANDSum(vector<int>& nums, int numSlots) {
    const int n = 2 * numSlots;
    const int nSelected = 1 << n;
    // dp[i] := the maximum value, where i is the bitmask of the selected
    // numbers
    vector<int> dp(nSelected);

    nums.resize(n);

    for (unsigned mask = 1; mask < nSelected; ++mask) {
      const int selected = popcount(mask);
      const int slot = (selected + 1) / 2;  // (1, 2) -> 1, (3, 4) -> 2
      for (int i = 0; i < n; ++i)
        if (mask >> i & 1)  // Assign `nums[i]` to the `slot`-th slot.
          dp[mask] = max(dp[mask], dp[mask ^ 1 << i] + (slot & nums[i]));
    }

    return dp.back();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int maximumANDSum(int[] nums, int numSlots) {
    final int n = 2 * numSlots;
    final int nSelected = 1 << n;
    // dp[i] := the maximum value, where i is the bitmask of the selected
    // numbers
    int[] dp = new int[nSelected];
    int[] A = Arrays.copyOf(nums, n);

    for (int mask = 1; mask < nSelected; ++mask) {
      final int selected = Integer.bitCount(mask);
      final int slot = (selected + 1) / 2; // (1, 2) -> 1, (3, 4) -> 2
      for (int i = 0; i < n; ++i)
        if ((mask >> i & 1) == 1) // Assign `A[i]` to the `slot`-th slot.
          dp[mask] = Math.max(dp[mask], dp[mask ^ 1 << i] + (slot & A[i]));
    }

    return dp[nSelected - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
    n = 2 * numSlots
    nSelected = 1 << n
    # dp[i] := the maximum value, where i is the bitmask of the selected
    # numbers
    dp = [0] * nSelected

    nums += [0] * (n - len(nums))

    for mask in range(1, nSelected):
      selected = mask.bit_count()
      slot = (selected + 1) // 2  # (1, 2) -> 1, (3, 4) -> 2
      for i, num in enumerate(nums):
        if mask >> i & 1:  # Assign `nums[i]` to the `slot`-th slot.
          dp[mask] = max(dp[mask], dp[mask ^ 1 << i] + (slot & num))

    return dp[-1]