Leetcode3287：求出数组中最大序列值
题目描述：
给你一个整数数组 nums 和一个 正 整数 k 。
定义长度为 2 * x 的序列 seq 的 值 为：
(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1]).
请你求出 nums 中所有长度为 2 * k 的子序列的 最大值 。
代码思路：
-
计算数组中所有数的按位或结果：
mx = reduce(lambda x,y : x | y, nums)这一步是为了确定所有可能的按位或结果的上限，因为任何数的按位或结果不会超过这个上限。
-
初始化动态规划数组：
f数组用于存储从数组右半部分选择j个数，能否通过按位或得到某个值x。f[i][j][x]表示在nums[i]到nums[n-1]中选择j个数，能否通过按位或得到x。pre数组用于存储从数组左半部分选择j个数，能否通过按位或得到某个值x。pre[i][j][x]表示在nums[0]到nums[i]中选择j个数，能否通过按位或得到x。
-
填充
f数组（从右向左遍历数组）：- 通过动态规划，从右向左遍历数组，更新
f数组。 - 对于每个位置
i和每个可能的选取数量j，以及每个可能的按位或结果x，检查是否可以通过加入当前数nums[i]来更新结果。
- 通过动态规划，从右向左遍历数组，更新
-
填充
pre数组（从左向右遍历数组）：- 使用类似的方法从左向右遍历数组，更新
pre数组。
- 使用类似的方法从左向右遍历数组，更新
-
计算最终结果：
- 遍历所有可能的分割点
i，将数组分为左半部分和右半部分。 - 对于每个分割点，检查左半部分和右半部分能否分别通过选取
k个数得到某个值x和y。 - 计算
x ^ y并更新最大值ans。
- 遍历所有可能的分割点
-
返回结果：
- 返回计算得到的最大值
ans。
- 返回计算得到的最大值
代码实现：
class Solution:
def maxValue(self, nums: List[int], k: int) -> int:
mx = reduce(lambda x,y : x | y,nums)
n = len(nums)
# f[i][j][x] 表示 在nums[i] - nums[n - 1] 中选 j 个数 or, 能否等于x
f = [[False] * (mx + 1) for _ in range(k + 1)]
f[0][0] = True
suf = [None] * n
# 下界是 k - 1 的原因是，f 是计算右半部分的，要留 k 个数字给 左半部分
for i in range(n - 1,k - 1,-1):
v = nums[i]
# 遍历到 i 时，f[i] 这一层的值都没更新，用的是 f[i + 1]的值来更新 f[i]
# 意思是，遍历到 i 时，只是更新 f[i], 不会用 f[i] 去更新别人
for j in range(k - 1,-1,-1):
for x,is_true in enumerate(f[j]):
if is_true: # f[i + 1][j][x] = true
f[j + 1][x | v] = True # 更新 f[i][j + 1][x | v] = true
suf[i] = f[k].copy()
# pre[i][j][x] 表示 在nums[0] - nums[i] 中选 j 个数 or, 能否等于x
pre = [[False] * (mx + 1) for _ in range(k + 1)]
pre[0][0] = True
ans = 0
for i in range(n - k):
v = nums[i]
for j in range(k - 1,-1,-1):
for x,is_true in enumerate(pre[j]):
if is_true: # pre[i - 1][j][x] = true
pre[j + 1][x | v] = True # 更新 pre[i][j + 1][x | v] = true
if i < k - 1:
continue
for x,is_truex in enumerate(pre[k]): # pre[i][k]
if is_truex:
for y,is_truey in enumerate(suf[i + 1]): # f[i + 1][k]
if is_truey:
# print(x,y)
ans = max(ans,x ^ y)
return ans