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 的子序列的 最大值 。

代码思路：

1. 计算数组中所有数的按位或结果：

   mx = reduce(lambda x,y : x | y, nums)

   这一步是为了确定所有可能的按位或结果的上限，因为任何数的按位或结果不会超过这个上限。

2. 初始化动态规划数组：

   • 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。

3. 填充 f 数组（从右向左遍历数组）：

   • 通过动态规划，从右向左遍历数组，更新 f 数组。
   • 对于每个位置 i 和每个可能的选取数量 j，以及每个可能的按位或结果 x，检查是否可以通过加入当前数 nums[i] 来更新结果。

4. 填充 pre 数组（从左向右遍历数组）：

   • 使用类似的方法从左向右遍历数组，更新 pre 数组。

5. 计算最终结果：

   • 遍历所有可能的分割点 i，将数组分为左半部分和右半部分。
   • 对于每个分割点，检查左半部分和右半部分能否分别通过选取 k 个数得到某个值 x 和 y。
   • 计算 x ^ y 并更新最大值 ans。

6. 返回结果：

   • 返回计算得到的最大值 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, 能否等于xf = [[False] * (mx + 1) for _ in range(k + 1)]f[0][0] = Truesuf = [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, 能否等于xpre = [[False] * (mx + 1) for _ in range(k + 1)]pre[0][0] = Trueans = 0for 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] = truepre[j + 1][x | v] = True  # 更新 pre[i][j + 1][x | v] = true if i < k - 1:continuefor 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