Leetcode 3287. Find the Maximum Sequence Value of Array

• Leetcode 3287. Find the Maximum Sequence Value of Array
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3287. Find the Maximum Sequence Value of Array

1. 解题思路

这一题我的思路比较暴力，就是求出每一个位置前后所有可能的长度为k的子序列的所有的或结果，然后两两求异或结果取最大值。

万幸还是侥幸可以通过所有测试样例的。

2. 代码实现

给出python代码实现如下：

class Solution:def maxValue(self, nums: List[int], k: int) -> int:n = len(nums)prefix = defaultdict(lambda: defaultdict(set))for i in range(n):for j in range(1, k+1):prefix[i][j] = deepcopy(prefix[i-1][j])if j == 1:prefix[i][j].add(nums[i])else:for elem in prefix[i-1][j-1]:prefix[i][j].add(elem | nums[i])suffix = defaultdict(lambda: defaultdict(set))for i in range(n-1, -1, -1):for j in range(1, k+1):suffix[i][j] = deepcopy(suffix[i+1][j])if j == 1:suffix[i][j].add(nums[i])else:for elem in suffix[i+1][j-1]:suffix[i][j].add(elem | nums[i])ans = 0for i in range(k-1, n-k):for left in prefix[i][k]:for right in suffix[i+1][k]:ans = max(ans, left^right)return ans

提交代码评测得到：耗时11887ms，占用内存547.7MB。