Skip to content

3277. Maximum XOR Score Subarray Queries 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  vector<int> maximumSubarrayXor(vector<int>& nums,
                                 vector<vector<int>>& queries) {
    const int n = nums.size();
    vector<int> ans;
    // xors[i][j] := the XOR score of nums[i..j]
    vector<vector<int>> xors(n, vector<int>(n));
    // dp[i][j] := the maximum XOR score of nums[i..j]
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
      xors[i][i] = nums[i];
      dp[i][i] = nums[i];
    }

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        xors[i][j] = xors[i][j - 1] ^ xors[i + 1][j];
        dp[i][j] = max({xors[i][j], dp[i][j - 1], dp[i + 1][j]});
      }

    for (const vector<int>& query : queries) {
      const int l = query[0];
      const int r = query[1];
      ans.push_back(dp[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
23
24
25
26
27
28
29
30
class Solution {
  public int[] maximumSubarrayXor(int[] nums, int[][] queries) {
    final int n = nums.length;
    int[] ans = new int[queries.length];
    // xors[i][j] := the XOR score of nums[i..j]
    int[][] xors = new int[n][n];
    // dp[i][j] := the maximum XOR score of nums[i..j]
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; ++i) {
      xors[i][i] = nums[i];
      dp[i][i] = nums[i];
    }

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        xors[i][j] = xors[i][j - 1] ^ xors[i + 1][j];
        dp[i][j] = Math.max(xors[i][j], Math.max(dp[i][j - 1], dp[i + 1][j]));
      }

    for (int i = 0; i < queries.length; ++i) {
      final int l = queries[i][0];
      final int r = queries[i][1];
      ans[i] = dp[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
23
class Solution:
  def maximumSubarrayXor(
      self,
      nums: list[int],
      queries: list[list[int]]
  ) -> list[int]:
    n = len(nums)
    # xors[i][j] := the XOR score of nums[i..j]
    xors = [[0] * n for _ in range(n)]
    # dp[i][j] := the maximum XOR score of nums[i..j]
    dp = [[0] * n for _ in range(n)]

    for i, num in enumerate(nums):
      xors[i][i] = num
      dp[i][i] = num

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        xors[i][j] = xors[i][j - 1] ^ xors[i + 1][j]
        dp[i][j] = max(xors[i][j], dp[i][j - 1], dp[i + 1][j])

    return [dp[l][r] for l, r in queries]