摘要
Title: 3287. 求出数组中最大序列值
Categories: 前后缀分解、dp

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

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 的子序列的 最大值 。

思路

经典的前后缀分解的题目，给出分界线，分别求出求出前面和后面的OR的所有值

抽象出子问题：数组长度为n，求出[0, j] (k-1 <= j < n - k) 的子序列的所有或值（从k-1开始是因为前面的凑不成k个数，到n-k是因为要留给后面k个数）
比如序列 [55, 85, 19, 6]，k=2，那么j需要从下标1开始，{55, 85}的或为 {119}，{55, 85, 19}的或（任意k个组成）为{55, 87, 119}；{55, 85, 19, 6} 为 {23, 55, 87, 119}
具体实现的思路就是设定dp数组，表示长度为i的数组的或的值的集合，那么比如{55, 85, 19}的或值就可以从{55, 85}推过来，也就是让dp数组，从后到前，dp[j].update({val | 19 for val in dp[j - 1]})

子问题解决完了，先从前往后，然后我们在从后往前预处理一下，这样就是一个前后缀分解的问题了
前后对应的两个集合中的数，分别进行异或操作，求最大值

代码

'''
Author: NEFU AB-IN
Date: 2024-09-14 22:24:42
FilePath: \LeetCode\CP139_2\c\c.py
LastEditTime: 2024-09-14 23:51:29
'''
# 3.8.9 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def maxValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = Arr.array(set, k + 1)
        dp[0].add(0)

        for num in nums[:k]:
            for j in range(k, 0, -1):
                for val in dp[j - 1]:
                    dp[j].add(val | num)

        res1 = [dp[k].copy()]
        for i in range(k, n - k):
            new_num = nums[i]
            for j in range(k, 0, -1):
                dp[j].update({val | new_num for val in dp[j - 1]})
            res1.append(dp[k].copy())

        dp = Arr.array(set, k + 1)
        dp[0].add(0)

        for num in reversed(nums[-k:]):
            for j in range(k, 0, -1):
                for val in dp[j - 1]:
                    dp[j].add(val | num)

        res2 = [dp[k].copy()]
        for i in range(n - k - 1, k - 1, -1):
            new_num = nums[i]
            for j in range(k, 0, -1):
                dp[j].update({val | new_num for val in dp[j - 1]})
            res2.append(dp[k].copy())

        res2 = res2[::-1]
        
        max_xor = 0
        for x, y in zip(res1, res2):
            for xx in x:
                for yy in y:
                    max_xor = Math.max(max_xor, xx ^ yy)
        
        return max_xor