2025-04-18：求出数组中最大序列值。用go语言，给定一个整数数组 nums 和一个正整数 k。 定义一个长度为 2*k

2025-04-18：求出数组中最大序列值。用go语言，给定一个整数数组 nums 和一个正整数 k。 定义一个长度为 2*k 的子序列 seq 的值为：

1.将 seq 的前 k 个元素依次做按位或运算，得到一个值；

2.将 seq 的后 k 个元素依次做按位或运算，得到另一个值；

3.然后将这两个结果做按位异或（XOR），得到 seq 的最终值。

任务是从 nums 中的所有长度为 2*k 的连续子序列中，找出使上述计算值最大的那个，并返回该最大值。

2 <= nums.length <= 400。

1 <= nums[i] < 128。

1 <= k <= nums.length / 2。

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

输出：5。

解释：

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

题目来自leetcode3287。

1. 题目理解与问题拆解

• • 给定一个整数数组 nums 和一个正整数 k。
• • 在 nums 中，寻找所有长度为 2*k 的连续子序列。
• • 对每个子序列进行如下运算：
  • • 计算子序列前 k 个元素的“按位或”值（即从第一个到第k个元素的或）。
  • • 计算子序列后 k 个元素的“按位或”值（即从第k+1个到第2*k个元素的或）。
  • • 对这两个“按位或”的结果做“异或”运算，得到当前子序列的值。
• • 在所有可能的连续子序列中，找到最大这样的值。

2. 整体算法设计思路

2.1 预处理子序列的按位或结果

• • 题目核心在于高效获得所有长度为 k 的连续子序列的按位或结果。
• • 原始思路是枚举所有长度为 k 的子序列，计算按位或。如果直接暴力计算，时间复杂度会较高（O(nkn)）。

2.2 动态规划（DP）求所有长度为k的子序列按位或

• • 代码中定义了内部函数 findORs(nums, k)，其目的是：
  • • 针对整个数组 nums，对于每个前缀位置 i，计算所有以 i 结尾的长度为 k 子序列的按位或结果集合。
  • • dp 结构是一个数组，dp[i] 存储所有以 nums[i] 结尾的长度为 k 子序列的按位或结果（用map[int]bool表示set结构，记录不同的按位或值）。
• • 动态规划状态转移：
  • • 定义 prev[j] 表示选择了 j 个元素时，所有能够得到的按位或值集合。
  • • 初始时 prev[0] 包含0（未选择元素）。
  • • 遍历数组元素，对于每个元素，逆序从j = min(k-1, i+1)到0遍历，
    • • 通过将当前元素和之前选择的结果做按位或，更新prev[j+1]。
  • • 当遍历完每个元素后，prev[k]中包含了所有长度为 k 的子序列的按位或结果的集合。
  • • 把prev[k]拷贝到对应的dp位置，表示以当前元素结尾的长度为k子序列的按位或集合。

2.3 分别计算左侧和右侧的按位或集合

• • 利用 findORs 计算数组从左向右的所有长度为 k 子序列的按位或结果，保存在 A。
• • 反转 nums 数组，再调用 findORs，得到从右向左的所有长度为 k 子序列的按位或结果集合，保存在 B。
• • 这里通过反转数组，简化了从后向前子序列计算的逻辑。

2.4 枚举“切分点”计算最大异或

• • 对数组中的位置 i 从 k-1 到 len(nums)-k-1 遍历：
  • • 此处 i 表示左边长度为 k 子序列的结尾索引，下一个索引开始为右边长度 k 子序列的起点（连续且不重叠）。
  • • 枚举 A[i] 中所有按位或结果 a，和 B[len(nums)-i-2] 中所有结果 b。
  • • 计算 a XOR b，更新最大值 mx。

3. 关键点总结

• • 通过动态规划+集合剪枝高效收集所有长度 k 子序列的按位或结果，避免重复计算。
• • 双向处理：从左向右和从右向左分别获取子序列按位或集合，便于快速计算两段子序列异或。
• • 枚举切分点使左右子序列连续且互不重叠，保证切割合理。
• • 最终找到符合条件的最大异或值。

4. 时间复杂度分析

• • 数组长度设为 n，子序列长度为 k。
• • 在 findORs 函数中，核心循环最多遍历 n 个元素，每个元素对 k 个子序列长度进行更新。
• • 对于每个 prev[j]集合中存储按位或结果的数量：由于 nums[i] < 128，按位或的最大范围是 7 位二进制，总共最多 2^7=128 个不同的按位或值。
• • 因此，每个 prev[j] 集合大小最多为 128。
• • 故对于每个元素，更新操作大约为 k * 128 次，整体为 O(n * k * 128)，可简写为 O(n * k)。
• • 计算两个方向的 findORs 各执行一次，总共 O(2 * n * k)，即 O(n * k) 。
• • 最后双重循环枚举两个集合的结果，最坏可能 A[i] 和 B[j] 集合大小均为最多约 128，因此这部分为 O(n * 128 * 128) ≈ O(n) ，常数因子较大但与128无关的情况下视作常数。
• • 总体时间复杂度：O(n * k + n) ≈ O(n * k)，其中k ≤ n/2。

5. 空间复杂度分析

• • dp 向量大小为 n，每个元素是一个 map/set，大小约为 128。
• • 因为存储每个位置的长度k子序列所有可能按位或结果。
• • 两个方向（A和B）都存储相同大小。
• • 额外空间主要由 A 和 B 占据，为 O(n * 128 * 2) ≈ O(n)。
• • 其他辅助空间如 prev 同理，大小为 k+1，每个元素也是大小上限128的集合。
• • 综合空间复杂度为 O(n * 128) ≈ O(n)，相较于输入规模线性。

6. 总结

以上为该算法的详细实现思路及复杂度分析。

Go完整代码如下：

package main

import (
    "fmt"
)

func maxValue(nums []int, k int)int {
    findORs := func(nums []int, k int) []map[int]bool {
        dp := make([]map[int]bool, 0)
        prev := make([]map[int]bool, k+1)
        for i := 0; i <= k; i++ {
            prev[i] = make(map[int]bool)
        }
        prev[0][0] = true

        for i := 0; i < len(nums); i++ {
            for j := min(k-1, i+1); j >= 0; j-- {
                for x := range prev[j] {
                    prev[j+1][x|nums[i]] = true
                }
            }
            current := make(map[int]bool)
            for key := range prev[k] {
                current[key] = true
            }
            dp = append(dp, current)
        }
        return dp
    }

    A := findORs(nums, k)
    reverse(nums)
    B := findORs(nums, k)
    mx := 0

    for i := k - 1; i < len(nums)-k; i++ {
        for a := range A[i] {
            for b := range B[len(nums)-i-2] {
                if a^b > mx {
                    mx = a ^ b
                }
            }
        }
    }
    return mx
}

func reverse(nums []int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

func main() {
    nums := []int{2, 6, 7}
    k := 1
    results := maxValue(nums, k)
    fmt.Println(results)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing importList

defmax_value(nums: List[int], k: int) -> int:
    deffind_ors(nums: List[int], k: int) -> List[set]:
        dp = []
        prev = [set() for _ inrange(k+1)]
        prev[0].add(0)

        for i inrange(len(nums)):
            for j inrange(min(k-1, i) , -1, -1):
                for x in prev[j]:
                    prev[j+1].add(x | nums[i])

            current = set(prev[k])
            dp.append(current)
        return dp

    defreverse(nums: List[int]) -> None:
        nums.reverse()

    A = find_ors(nums, k)
    reverse(nums)
    B = find_ors(nums, k)

    mx = 0
    n = len(nums)
    for i inrange(k-1, n - k):
        for a in A[i]:
            for b in B[n - i - 2]:
                mx = max(mx, a ^ b)
    return mx

if __name__ == "__main__":
    nums = [2, 6, 7]
    k = 1
    print(max_value(nums, k))