What is the key idea to solve Maximum AND Sum of Array?

Use state transition dynamic programming with bitmasking to track slot occupancy and maximize AND sum.

Can greedy approaches work for this problem?

Greedy methods usually fail because placing numbers sequentially may miss optimal AND sum combinations.

How do I encode slot occupancy for DP?

Use a ternary digit per slot to represent 0,1,2 numbers in a slot, forming a bitmask for state transitions.

Is there a memory-efficient way to handle DP states?

Yes, store only states that are reachable and prune states exceeding slot limits to save space.

Does this approach generalize to OR sum variants?

Yes, similar DP with bitmask works, but the sum calculation changes from AND to OR for each number and slot.

#2172

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

数组的最大与和

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足 2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。你需要把所有 n 个整数分到这些篮子中，且每个篮子至多有 2 个整数。一种分配方案的与和定义为每个数与…

数组动态规划位运算位掩码

题目描述

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。

你需要把所有 n 个整数分到这些篮子中，且每个篮子至多有 2 个整数。一种分配方案的与和定义为每个数与它所在篮子编号的 按位与运算 结果之和。

比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中，这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。

请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。

示例 1：

输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。
最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。

示例 2：

输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

提示：

n == nums.length
1 <= numSlots <= 9
1 <= n <= 2 * numSlots
1 <= nums[i] <= 15

lightbulb

解题思路

方法一：状态压缩 + 动态规划

由于每个篮子最多只能放两个数，我们不妨将篮子数乘以 $2$ ，这样每个篮子最多只能放一个数。

接下来，我们定义 $f[i]$ 表示篮子状态为 $i$ 时的最大与和，其中 $i$ 是一个二进制数，表示每个篮子是否放了数。初始时 $f[0]=0$ 。

接下来，我们考虑 $f[i]$ 如何进行状态转移。

我们可以枚举 $i$ ，记 $i$ 的二进制表示中 $1$ 的个数为 $cnt$ 。如果 $cnt \gt n$ ，那么 $i$ 不是一个合法的状态，我们可以直接跳过。否则，我们可以枚举 $i$ 的二进制表示中的每一位 $j$ ，如果 $i$ 的第 $j$ 位为 $1$ ，那么我们可以将第 $(cnt-1)$ 个数 $nums[cnt-1]$ 放入第 $j$ 个篮子中，此时有：

f[i] = \max\{f[i], f[i \oplus (1 << j)] + (nums[cnt-1] \wedge (j / 2 + 1))\}

其中 $\oplus$ 表示异或运算，而 $\wedge$ 表示按位与运算。

答案为 $\max\{f[i]\}$ 。

时间复杂度 $O(4^k \times k \times 2)$ ，空间复杂度 $O(4^k)$ 。其中 $k$ 表示篮子的数量，即题目中的 $numSlots$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:
        n = len(nums)
        m = numSlots << 1
        f = [0] * (1 << m)
        for i in range(1 << m):
            cnt = i.bit_count()
            if cnt > n:
                continue
            for j in range(m):
                if i >> j & 1:
                    f[i] = max(f[i], f[i ^ (1 << j)] + (nums[cnt - 1] & (j // 2 + 1)))
        return max(f)

speed

复杂度分析

指标	值
时间	complexity is O(n * 3^numSlots) due to enumerating states and transitions for each number. Space complexity is O(3^numSlots) to store DP states representing slot occupancy counts.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about handling at most two numbers per slot.
question_mark
Hints at using dynamic programming with bitmasking.
question_mark
Probes understanding of AND operation impact on sum maximization.

warning

常见陷阱

外企场景

error
Forgetting the two-number limit per slot, causing invalid states.
error
Not encoding slot occupancy efficiently, leading to exponential memory use.
error
Assuming greedy placement works, which may miss optimal AND sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing variable slot capacities instead of fixed two per slot.
arrow_right_alt
Maximizing OR sum instead of AND sum with similar slot constraints.
arrow_right_alt
Limiting slot numbers further to increase DP state complexity.

help

常见问题

外企场景

继续练习

#2305 公平分发饼干 #2035 将数组分成两个数组并最小化数组和的差 #1994 好子集的数目