leetcode ====> 3287. 求出数组中最大序列值
计算后缀。对于 0-1 背包问题，我们定义 f[i][j][x] 表示从 nums[i] 到 nums[n − 1] 中选 j 个数，这些数的 OR 能否等于 x。
设 v = nums[i]，用刷表法转移：
- 不选 v，那么
f[i][j][x] = f[i+1][j][x]。 - 选 v，如果
f[i+1][j][x] = true，那么f[i][j + 1][x ∣ v] = true。
刷表法：本题计算 x=v ∣ ? 中的 ? 是困难的，但计算 x ∣ v 是很简单的。也就是说，对于状态 f[i][j][x] 而言，其转移来源是谁不好计算，但从 f[i][j][x] 转移到的目标状态 f[i][j + 1][x ∣ v] 是好计算的。在动态规划中，根据转移来源计算状态叫查表法，用当前状态更新其他状态叫刷表法。
class Solution:
def maxValue(self, nums: List[int], k: int) -> int:
# 学习两种dp方式，查表法和刷表法。本题只能用刷表法
m = 1 << 7
n = len(nums)
# f[i][j][k]: i表示前i个...
f = [[[False] * m for _ in range(k + 2)] for _ in range(n + 1)]
f[0][0][0] = True
for i in range(n):
for j in range(k + 1):
for x in range(m):
f[i + 1][j][x] |= f[i][j][x]
f[i + 1][j + 1][x | nums[i]] |= f[i][j][x]
g = [[[False] * m for _ in range(k + 2)] for _ in range(n + 1)]
# g[i][j][k]: i表示从下标i开始
g[n][0][0] = True
for i in range(n - 1, -1, -1):
for j in range(k + 1):
for y in range(m):
g[i][j][y] |= g[i + 1][j][y]
g[i][j + 1][y | nums[i]] |= g[i + 1][j][y]
ans = 0
for i in range(k, n - k + 1): # 这里i是前i个的意思，[k, n - k]
for x in range(m):
if f[i][k][x]: # 这里i表示的是前i个
for y in range(m):
if g[i][k][y]: # 这里g[i][][]的i表示从下标i开始
ans = max(ans, x ^ y)
return ans