-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
45 lines (39 loc) · 1.34 KB
/
Solution.cs
File metadata and controls
45 lines (39 loc) · 1.34 KB
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
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution
{
public int[] MaximumSubarrayXor(int[] nums, int[][] queries)
{
// Key 1: Xor score of nums[i..j] = nums[i..j-1] Xor(^) nums[i+1..j]
// Key 2: Get Max Xor score of nums[i..j] by using DP stored Xor score of all i->j
// DP[i][j] = Xor score of nums[i..j]
// Max Xor score = Max(DP[i][j], DP[i][j-1], DP[i+1][j])
int[][] dp = new int[nums.Length][];
for (int i = 0; i < nums.Length; i++)
{
dp[i] = new int[nums.Length];
Array.Fill(dp[i], 0);
dp[i][i] = nums[i];
}
for (int len = 2; len <= nums.Length; len++)
{
for (int st = 0; st + len - 1 < nums.Length; st++)
{
var end = st + len - 1;
dp[st][end] = dp[st][end - 1] ^ dp[st + 1][end];
}
}
for (int len = 2; len <= nums.Length; len++)
{
for (int st = 0; st + len - 1 < nums.Length; st++)
{
var end = st + len - 1;
dp[st][end] = Math.Max(dp[st][end], Math.Max(dp[st][end - 1], dp[st + 1][end]));
}
}
int[] result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++)
{
result[i] = dp[queries[i][0]][queries[i][1]];
}
return result;
}
}