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