题目:
思路:在已有的数组中寻找符合条件,也就是没有重复数字的子数组,以掩码的对应位的形式来表示当前子数组元素的存在,之后双重循环生成所有子数组,内层循环中,判断当前元素是否存在掩码中,存在则推出,不存在则加入掩码并标记。用另一个循环来更新 sum 数组,使得每个掩码的值能反映其对应的最大元素数量。之后遍历所有掩码,计算其和补码的元素之和挑最大的那个输出即可。(ps:这种题目真的是人做的吗?)
程序:
def main():
n = int(input())
arr = list(map(int, input().split()))
sum_masks = [0] * (1 << 18)
is_mask = [0] * (1 << 18)
for l in range(n):
mask = 0
for r in range(l, n):
if (mask >> (arr[r] - 1)) & 1:
break
mask |= (1 << (arr[r] - 1))
sum_masks[mask] = bin(mask).count('1')
is_mask[mask] = 1
for i in range(18):
for j in range(1 << 18):
if (j >> i) & 1:
sum_masks[j] = max(sum_masks[j], sum_masks[j - (1 << i)])
ans = 0
for i in range(1 << 18):
if is_mask[i]:
ans = max(ans, bin(i).count('1') + sum_masks[((1 << 18) - 1) ^ i])
print(ans)
if name == "main":
main()