2026-06-17：最大子数组异或值。用go语言，给定一个非负整数数组 nums 和一个整数 k。你需要从中挑选任意一个连续非空子数组，使得该子数

package main

import (
    "fmt"
    "math/bits"
)

func maxXor(nums []int, k int) (ans int) {
    // 预处理：当窗口右端点在 right 时，窗口左端点在 lefts[right]
    // 顺带算出前缀异或和、nums 的最大值
    n := len(nums)
    lefts := make([]int, n)
    sum := make([]int, len(nums)+1)
    mx := 0
    var minQ, maxQ []int
    left := 0
    for right, x := range nums {
        sum[right+1] = sum[right] ^ x
        mx = max(mx, x)

        // 1. 入
        forlen(minQ) > 0 && x <= nums[minQ[len(minQ)-1]] {
            minQ = minQ[:len(minQ)-1]
        }
        minQ = append(minQ, right)

        forlen(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {
            maxQ = maxQ[:len(maxQ)-1]
        }
        maxQ = append(maxQ, right)

        // 2. 出
        for nums[maxQ[0]]-nums[minQ[0]] > k {
            left++
            if minQ[0] < left {
                minQ = minQ[1:]
            }
            if maxQ[0] < left {
                maxQ = maxQ[1:]
            }
        }

        // 3. 记录此时的 left
        lefts[right] = left
    }

    // 试填法
    width := bits.Len(uint(mx))
    last := make([]int, 1<<width)
    for i := width - 1; i >= 0; i-- {
        for j := range1 << (width - i) {
            last[j] = -1
        }
        last[0] = 0// sum[0] = 0 的位置是 0
        ans <<= 1
        newAns := ans | 1
        for right, l := range lefts {
            s := sum[right+1] >> i   // 去掉低位，只看高位
            if last[newAns^s] >= l { // newAns^s 存在，且在窗口内
                ans = newAns // 最终答案第 i 位填 1
                break
            }
            last[s] = right + 1
        }
    }

    return
}

func main() {
    nums := []int{5, 4, 5, 6}
    k := 2
    result := maxXor(nums, k)
    fmt.Println(result)
}

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

from typing import List

def maxXor(nums: List[int], k: int) -> int:
    n = len(nums)
    lefts = [0] * n
    prefix_sum = [0] * (n + 1)
    mx = 0
    
    # 单调队列求窗口左端点
    min_q = []
    max_q = []
    left = 0
    
    for right, x in enumerate(nums):
        prefix_sum[right + 1] = prefix_sum[right] ^ x
        mx = max(mx, x)
        
        # 入队
        while min_q and x <= nums[min_q[-1]]:
            min_q.pop()
        min_q.append(right)
        
        while max_q and x >= nums[max_q[-1]]:
            max_q.pop()
        max_q.append(right)
        
        # 出队
        while nums[max_q[0]] - nums[min_q[0]] > k:
            left += 1
            if min_q[0] < left:
                min_q.pop(0)
            if max_q[0] < left:
                max_q.pop(0)
        
        # 记录此时的左端点
        lefts[right] = left
    
    # 试填法求最大异或值
    width = mx.bit_length()
    ans = 0
    
    for i in range(width - 1, -1, -1):
        # 初始化 last 数组
        last = [-1] * (1 << (width - i))
        last[0] = 0  # prefix_sum[0] = 0 的位置是 0
        
        ans <<= 1
        new_ans = ans | 1
        found = False
        
        for right, l in enumerate(lefts):
            s = prefix_sum[right + 1] >> i  # 去掉低位，只看高位
            if last[new_ans ^ s] >= l:  # new_ans^s 存在，且在窗口内
                ans = new_ans  # 最终答案第 i 位填 1
                found = True
                break
            last[s] = right + 1
        
        if not found:
            # 如果没找到，ans 保持原样（第 i 位为 0）
            pass
    
    return ans


def main():
    nums = [5, 4, 5, 6]
    k = 2
    result = maxXor(nums, k)
    print(result)


if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <cmath>

using namespace std;

int maxXor(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> lefts(n);
    vector<int> prefix_sum(n + 1, 0);
    int mx = 0;

    // 单调队列求窗口左端点
    deque<int> min_q, max_q;
    int left = 0;

    for (int right = 0; right < n; right++) {
        int x = nums[right];
        prefix_sum[right + 1] = prefix_sum[right] ^ x;
        mx = max(mx, x);

        // 入队
        while (!min_q.empty() && x <= nums[min_q.back()]) {
            min_q.pop_back();
        }
        min_q.push_back(right);

        while (!max_q.empty() && x >= nums[max_q.back()]) {
            max_q.pop_back();
        }
        max_q.push_back(right);

        // 出队
        while (nums[max_q.front()] - nums[min_q.front()] > k) {
            left++;
            if (min_q.front() < left) {
                min_q.pop_front();
            }
            if (max_q.front() < left) {
                max_q.pop_front();
            }
        }

        // 记录此时的左端点
        lefts[right] = left;
    }

    // 试填法求最大异或值
    int width = 0;
    int temp = mx;
    while (temp > 0) {
        width++;
        temp >>= 1;
    }
    if (width == 0) width = 1; // 处理 mx = 0 的情况

    int ans = 0;

    for (int i = width - 1; i >= 0; i--) {
        // 初始化 last 数组
        int last_size = 1 << (width - i);
        vector<int> last(last_size, -1);
        last[0] = 0; // prefix_sum[0] = 0 的位置是 0

        ans <<= 1;
        int new_ans = ans | 1;
        bool found = false;

        for (int right = 0; right < n; right++) {
            int l = lefts[right];
            int s = prefix_sum[right + 1] >> i; // 去掉低位，只看高位

            // 检查 new_ans ^ s 是否存在，且在窗口内
            if (last[new_ans ^ s] >= l) {
                ans = new_ans; // 最终答案第 i 位填 1
                found = true;
                break;
            }
            last[s] = right + 1;
        }

        // 如果没找到，ans 保持原样（第 i 位为 0）
    }

    return ans;
}

int main() {
    vector<int> nums = {5, 4, 5, 6};
    int k = 2;
    int result = maxXor(nums, k);
    cout << result << endl;
    return0;
}