因为要求整体子数组分数之和尽可能小,全局贪心可得到局部贪心,因此每个子数组的 $AND$都要很小,由于按位与运算只会越与越单调不增,因此遍历数组,如果与的结果为 $0$,说明需要多开一个子数组,否则继续进行与运算
由于 $a[i]$ 是小于$10^6$,二进制$20$个$1$的值为$1048575$,是大于 $10^6$中最小的二进制位全为$1$的数,选它是由于 $1048575$与 $a[i]$任何值按位与运算都是 $a[i]$
Java代码:
class Solution {
public int maxSubarrays(int[] a) {
int res = 0, s = 1048575; // 2 ^ 20 - 1
for (var x : a) {
s &= x;
if (s == 0) {
res ++;
s = 1048575;
}
}
return Math.max(res, 1);
}
}
Go代码:
func maxSubarrays(a []int) int {
res, s := 0, 1048575
for _, x := range a {
s &= x
if s == 0 {
res ++
s = 1048575
}
}
return max(res, 1)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}