Skip to content

3277. Maximum XOR Score Subarray Queries

Description

You are given an array nums of n integers, and a 2D integer array queries of size q, where queries[i] = [li, ri].

For each query, you must find the maximum XOR score of any subarray of nums[li..ri].

The XOR score of an array a is found by repeatedly applying the following operations on a so that only one element remains, that is the score:

  • Simultaneously replace a[i] with a[i] XOR a[i + 1] for all indices i except the last one.
  • Remove the last element of a.

Return an array answer of size q where answer[i] is the answer to query i.

 

Example 1:

Input: nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

Output: [12,60,60]

Explanation:

In the first query, nums[0..2] has 6 subarrays [2], [8], [4], [2, 8], [8, 4], and [2, 8, 4] each with a respective XOR score of 2, 8, 4, 10, 12, and 6. The answer for the query is 12, the largest of all XOR scores.

In the second query, the subarray of nums[1..4] with the largest XOR score is nums[1..4] with a score of 60.

In the third query, the subarray of nums[0..5] with the largest XOR score is nums[1..4] with a score of 60.

Example 2:

Input: nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

Output: [7,14,11,14,5]

Explanation:

Index nums[li..ri] Maximum XOR Score Subarray Maximum Subarray XOR Score
0 [0, 7, 3, 2] [7] 7
1 [7, 3, 2, 8, 5] [7, 3, 2, 8] 14
2 [3, 2, 8] [3, 2, 8] 11
3 [3, 2, 8, 5, 1] [2, 8, 5, 1] 14
4 [5, 1] [5] 5

 

Constraints:

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 231 - 1
  • 1 <= q == queries.length <= 105
  • queries[i].length == 2
  • queries[i] = [li, ri]
  • 0 <= li <= ri <= n - 1

Solutions

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent the XOR value of $\textit{nums}[i..j]$. According to the problem description, we can derive the state transition equation:

$$ f[i][j] = f[i][j-1] \oplus f[i+1][j] $$

where $\oplus$ denotes the XOR operation.

We further define $g[i][j]$ to represent the maximum value of $f[i][j]$. The state transition equation is:

$$ g[i][j] = \max(f[i][j], g[i][j-1], g[i+1][j]) $$

Finally, we traverse the query array. For each query $[l, r]$, we add $g[l][r]$ to the answer array.

The time complexity is $O(n^2 + m)$, and the space complexity is $O(n^2)$. Here, $n$ and $m$ are the lengths of the arrays $\textit{nums}$ and $\textit{queries}$, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maximumSubarrayXor(
        self, nums: List[int], queries: List[List[int]]
    ) -> List[int]:
        n = len(nums)
        f = [[0] * n for _ in range(n)]
        g = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            f[i][i] = g[i][i] = nums[i]
            for j in range(i + 1, n):
                f[i][j] = f[i][j - 1] ^ f[i + 1][j]
                g[i][j] = max(f[i][j], g[i][j - 1], g[i + 1][j])
        return [g[l][r] for l, r in queries]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] maximumSubarrayXor(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] f = new int[n][n];
        int[][] g = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            f[i][i] = nums[i];
            g[i][i] = nums[i];
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = f[i][j - 1] ^ f[i + 1][j];
                g[i][j] = Math.max(f[i][j], Math.max(g[i][j - 1], g[i + 1][j]));
            }
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = g[l][r];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<vector<int>> f(n, vector<int>(n));
        vector<vector<int>> g(n, vector<int>(n));
        for (int i = n - 1; i >= 0; --i) {
            f[i][i] = nums[i];
            g[i][i] = nums[i];
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = f[i][j - 1] ^ f[i + 1][j];
                g[i][j] = max({f[i][j], g[i][j - 1], g[i + 1][j]});
            }
        }
        vector<int> ans;
        for (const auto& q : queries) {
            int l = q[0], r = q[1];
            ans.push_back(g[l][r]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maximumSubarrayXor(nums []int, queries [][]int) (ans []int) {
    n := len(nums)
    f := make([][]int, n)
    g := make([][]int, n)
    for i := 0; i < n; i++ {
        f[i] = make([]int, n)
        g[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i-- {
        f[i][i] = nums[i]
        g[i][i] = nums[i]
        for j := i + 1; j < n; j++ {
            f[i][j] = f[i][j-1] ^ f[i+1][j]
            g[i][j] = max(f[i][j], max(g[i][j-1], g[i+1][j]))
        }
    }
    for _, q := range queries {
        l, r := q[0], q[1]
        ans = append(ans, g[l][r])
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maximumSubarrayXor(nums: number[], queries: number[][]): number[] {
    const n = nums.length;
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    const g: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        f[i][i] = nums[i];
        g[i][i] = nums[i];
        for (let j = i + 1; j < n; j++) {
            f[i][j] = f[i][j - 1] ^ f[i + 1][j];
            g[i][j] = Math.max(f[i][j], Math.max(g[i][j - 1], g[i + 1][j]));
        }
    }
    return queries.map(([l, r]) => g[l][r]);
}

Comments