What is the minimum score for splitting an array in this problem?

The minimum score is the bitwise AND of all elements in the array, which every subarray must achieve in a valid split.

Can this problem be solved using dynamic programming?

While possible, dynamic programming is inefficient here; the greedy choice with invariant validation achieves optimal O(n) time.

Why do we reset the running AND after reaching the minimum score?

Resetting ensures each new subarray starts fresh, maintaining the invariant and allowing the maximum number of subarrays.

Does the order of elements affect the maximum subarray count?

Yes, since bitwise AND is order-sensitive, the greedy approach respects the original sequence to maintain correct minimum scores.

How does the greedy choice plus invariant validation pattern apply here?

The pattern ensures each subarray satisfies the minimum AND score as we scan, finalizing subarrays at the exact point the invariant is met.

#2871

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

将数组分割成最多数目的子数组

给你一个只包含非负整数的数组 nums 。我们定义满足 l 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。请你将数组分割成一个或者更多子数组，满足：每个元素都只属于一个子…

数组贪心位运算

题目描述

给你一个只包含非负整数的数组 nums 。

我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。

请你将数组分割成一个或者更多子数组，满足：

每个元素都只属于一个子数组。
子数组分数之和尽可能小。

请你在满足以上要求的条件下，返回最多可以得到多少个子数组。

一个 子数组 是一个数组中一段连续的元素。

示例 1：

输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。
在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。

示例 2：

输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。
在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：贪心 + 位运算

我们初始化一个变量 $score$ ，用来记录当前子数组的分数，初始时 $score = -1$ 。然后我们遍历数组，对于每个元素 $num$ ，我们将 $score$ 与 $num$ 进行按位与运算，然后将结果赋值给 $score$ 。如果 $score = 0$ ，说明当前子数组的分数为 $0$ ，我们就可以将当前子数组分割出来，然后将 $score$ 重置为 $-1$ 。最后我们返回分割出的子数组的个数。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        score, ans = -1, 1
        for num in nums:
            score &= num
            if score == 0:
                score = -1
                ans += 1
        return 1 if ans == 1 else ans - 1

speed

复杂度分析

指标	值
时间	complexity is O(n) since we scan the array once and perform constant-time bitwise operations per element. Space complexity is O(1) if only counters and a running AND are maintained, or O(n) if storing all subarrays explicitly.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on the greedy choice plus invariant validation pattern and its correctness.
question_mark
Expect clarity on why the bitwise AND of all elements determines the minimum score.
question_mark
Be ready to discuss failure modes if subarrays are merged incorrectly, reducing the maximum count.

warning

常见陷阱

外企场景

error
Attempting to split based on zero or any other arbitrary value instead of the computed minimum score.
error
Resetting the running AND incorrectly, which can merge subarrays violating the invariant.
error
Overcomplicating with dynamic programming instead of a direct greedy scan, increasing time and space unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize subarrays where each subarray's OR equals a target instead of AND.
arrow_right_alt
Split arrays to minimize the sum of squared bitwise AND scores instead of counting subarrays.
arrow_right_alt
Apply the greedy AND invariant method to a circular array scenario for extended pattern practice.

help

常见问题

外企场景

继续练习

#2897 对数组执行操作使平方和最大 #2835 使子序列的和等于目标的最少操作次数 #3022 给定操作次数内使剩余元素的或值最小