Problem: 3287. 求出数组中最大序列值

思路

1. 计算所有 下标 $j$ 前 $k$ 个数可能 $or$ 出的结果，记为$prefix[k-1][j+1][x]$
   因为$1 <= nums[j] < 2^7$，所以 $x < 2^7$
2. 同理，计算所有 下标 $j$ 后 $k$ 个数可能 $or$ 出的结果，记为$suffix[k-1][j][x]$
3. 枚举可能的分割位置 $i$ ，计算此位置前后的 $xor$ 值 = $prefix[i+1]$ ^ $suffix[i]$

Code

###Python3

class Solution:
    def maxValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mx = reduce(or_, nums)
        prefix = [[[False] * (mx + 1) for i in range(n + 1)] for j in range(k + 1)]
        ans = -inf
        # 1. prefix or for k
        for i in range(n):
            prefix[0][i + 1] = prefix[0][i].copy()
            prefix[0][i + 1][nums[i]] = True
        for i in range(1, k):
            for j in range(i, n - k + 1):
                x = nums[j]
                # unselect
                prefix[i][j + 1] = prefix[i][j].copy()
                # select
                for h in range(0, mx + 1):
                    if prefix[i - 1][j][h]:
                        prefix[i][j + 1][h | x] = True
            # print( f[i])
        # 2. suffix or for k
        suffix = [[[False] * (mx + 1) for i in range(n + 1)] for j in range(k + 1)]
        for i in range(n - 1, -1, -1):
            suffix[0][i] = suffix[0][i + 1].copy()
            suffix[0][i][nums[i]] = True

        for i in range(1, k):
            for j in range(n - 1, k - 1, -1):
                x = nums[j]
                # unselect
                suffix[i][j] = suffix[i][j + 1].copy()
                # select
                for h in range(0, mx + 1):
                    if suffix[i - 1][j + 1][h]:
                        suffix[i][j][h | x] = True

        # 3. 枚举 所有 prefix xor suffix
        ans = -inf
        for i in range(k - 1, n - k + 1):  # [0, i] [i+1, i+k]
            pre = prefix[k - 1][i + 1]
            for j in range(1, mx + 1):
                if not pre[j]:
                    continue
                post = suffix[k - 1][i + 1]
                for h in range(1, mx + 1):
                    if post[h]:
                        ans = max(ans, j ^ h)
        return ans

复杂度

• 时间复杂度: $O(nkU)$，$n$ 是 $nums$ 的长度，$U$ 是 $nums$ 所有元素的 $OR$，最多为 $2 ^ 7 -1$
• 空间复杂度: $O(nkU)$