142 子数组的最大异或和 - 程序员代码面试指南

即以i结尾的最大异或和就是0到某一位置x的异或结果和0-i异或结果最大，举个例子，假设x是3，0-3的异或结果和0-i进行异或得到的结果最大，那么就说明4-i的异或结果是最大的

0异或任何数都是这个数
0-1 ^ 0-3 = 2-3
0-1 ^ 0-2 = 2
0-0 ^ 0-3 = 1-3

所以问题最后转化为：求前缀异或和中每两个数的异或和最大的，初始需要前缀树中有个0

int整数，最高位是符号位(0为正数,1为负数),对于异或操作
只要符号位相同，后面31位相异的越多，那么最后异或操作得到的值就越大

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Trie{

    Node root = new Node();

    class Node{
        Node[] next;
        public Node() {
            next = new Node[2];
            for(int i=0;i<2;i++){
                next[i] = null;
            }
        }
    }

    // 将一个数加到字典树里面
    void add(int num){
        Node cur = root;
        for(int move = 31;move >= 0;move--) {
            int bit = ((num >> move) & 1);//每一位上的数字(0,1)
            if(cur.next[bit] == null){
                cur.next[bit] = new Node();
            }
            cur = cur.next[bit];
        }
    }

    // 判断num与字典树里面的所有值进行异或能得到的最大值
    int getMaxXOR(int num){
        Node cur = root;
        int res = 0;
        for(int move = 31;move >= 0;move--) {
            int bit = (num >> move) & 1;//提取每一位
            int bestBit; // 选择可能的最大树分支进行异或，符号位选择跟符号位一样的，非符号位选择跟当前不一样的
            if(move == 31){ // 符号位
                bestBit = bit;
            }else { // 非符号位
                bestBit = 1 ^ bit;
            }
            int realbit = bestBit; // 实际选择的可能没有, 那别无选择
            if(cur.next[bestBit] == null){
                realbit = bestBit ^ 1;
            }
            res = res | (bit ^ realbit) << move; // 设置res的每一位
            cur = cur.next[realbit]; //继续往下走
        }
        return res;
    }
}


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] preFix = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            if(i == 0) {
                preFix[i] = arr[i];
            }else {
                preFix[i] = preFix[i-1] ^ arr[i];
            }
        }
        int result = Integer.MIN_VALUE;
        Trie trie = new Trie();
        trie.add(0);
        for(int i=0;i<n;i++){
            result = Math.max(result, trie.getMaxXOR(preFix[i]));
            trie.add(preFix[i]);
        }
        System.out.println(result);
    }


}
/*
4
3 -28 -29 2

7

{-28，-29}这个子数组的异或和为7，是所有子数组中最大的
*/

ac

异或性质

前缀+利用异或性质

ac