给定一个整型数组arr,其中可能有正有负有零。你可以随意把整个数组切成若干个不相容的子数组,求异或和为0的子数组最多可能有多少个?整数异或和定义:把数组中所有的数异或起来得到的值。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
private static int solve(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
Map<Integer, Integer> helper = new HashMap<>();
int[] dp = new int[n];
helper.put(0, -1);
int sum = 0;
for (int i = 0; i < n; ++i) {
sum ^= arr[i];
Integer index = helper.get(sum);
dp[i] = i > 0 ? dp[i - 1] : 0;
if (index != null) {
dp[i] = Math.max(dp[i], 1 + (index >= 0 ? dp[index] : 0));
}
helper.put(sum, i);
}
return dp[n - 1];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = in.nextInt();
}
System.out.println(solve(arr));
}
}
}