Leetcode Problem 2172. Maximum AND Sum of Array

2172. Maximum AND Sum of Array

Leetcode Solutions

Bitmask Dynamic Programming Approach

  1. Initialize a DP array dp with size 1 << (2 * numSlots) and fill it with -1, representing uncalculated states.
  2. Define a recursive function solve that takes the current index of nums, the current state of the bitmask, and the number of slots.
  3. In solve, if the current index is equal to the length of nums, return 0 (base case).
  4. If the current state is already calculated in dp, return the stored value.
  5. Iterate over all slots. For each slot, check if it can take more numbers (i.e., its state is not 10).
  6. If the slot can take a number, update the bitmask to reflect the number placement and calculate the new AND sum.
  7. Recursively call solve with the next index and the updated bitmask.
  8. Take the maximum AND sum from all possibilities and store it in dp for the current state.
  9. The initial call will be solve(0, 0, numSlots).
  10. Return the value of dp with all bits set (all numbers placed).
UML Thumbnail

Simple Recursive Approach with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...