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

难度：困难

题目¶

给你一个整数数组 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：

输入：nums = [2,6,7], k = 1

输出：5

解释：

子序列 [2, 7] 的值最大，为 2 XOR 7 = 5 。

示例 2：

输入：nums = [4,2,5,6,7], k = 2

输出：2

解释：

子序列 [4, 5, 6, 7] 的值最大，为 (4 OR 5) XOR (6 OR 7) = 2 。

提示：

2 <= nums.length <= 400
1 <= nums[i] < 2^7
1 <= k <= nums.length / 2

Reference

题解¶

使用一个表dp_left[i][j] = set()分别存储从当前位置i开始（包括自身）向前选取j个元素后，对其取or操作的所有可能结果。dp_left[i][j]可以通过以下方式计算。

选择当前元素，则这部分的可能取值为[_ | current_value for _ in dp_left[i - 1][j - 1]]
不选择当前元素，则这部分的可能取值为dp_left[i - 1][j]

将这两部分合并，即可计算出dp_left[i][j]的取值。同理，可以按照相似的方法计算从当前位置i开始向后选取j个元素后对其取or操作的所有可能结果。

最终结果为遍历[0, length - 1)，比较dp_left[i][k]（i及i左侧）和dp_right[i + 1][k]（i右侧，不包含i）中各个可能取值的最大xor值。

import itertools

class Solution:
    def buildDp(self, nums: List[int], k: int):
        dp = [[{0}, *[set() for _ in range(k)]] for _ in nums]
        for i, value in enumerate(nums):
            for j in range(1, k + 1):
                if i >= 0:
                    dp[i][j] |= dp[i - 1][j]
                    dp[i][j] |= {_ | value for _ in dp[i - 1][j - 1]}
        return dp

    def maxValue(self, nums: List[int], k: int) -> int:
        dp_left = [_[k] for _ in self.buildDp(nums, k)]
        dp_right = [_[k] for _ in self.buildDp(nums[::-1], k)[::-1]]
        length = len(nums)
        max_value = -1

        for i in range(length - 1):
            for x, y in itertools.product(dp_left[i], dp_right[i + 1]):
                max_value = max(max_value, x ^ y)
        return max_value

时间复杂度和空间复杂度均较高，有待优化。

子序列 是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组。 ↩

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

题目¶

题解¶

评论