首页 > 试题广场 >

子数组的最大异或和

[编程题]子数组的最大异或和
  • 热度指数:1340 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
数组异或和的定义:把数组中所有的数异或起来得到的值。给定一个整型数组arr,其中可能有正、有负,有零,求其中子数组的最大异或和。

输入描述:
输出包含两行,第一行一个整数n,代表数组arr长度,第二个n个整数,代表数组arr


输出描述:
输出一个整数,代表其中子数组的最大异或和。
示例1

输入

4
3 -28 -29 2

输出

7

说明

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

备注:
时间复杂度,额外空间复杂度
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))

typedef struct tn {
    struct tn **children;  // 存放子节点的指针
} node;

node *new_node() {
    node *new_node = malloc(sizeof(node));
    new_node->children = (node **) calloc(2, sizeof(node *));
    return new_node;
}

void destroy_node(node *node) {
    free(node->children);
    free(node);
}

void destroy_whole_path(node *node) {
    destroy_node(node->children[0]);
    destroy_node(node->children[1]);
    destroy_node(node);
}

void insert(node *root, int num) {
    node *cur = root;
    int path;
    for (int move = 31; move >= 0; move--) {
        path = (num >> move) & 1;
        if (cur->children[path] == NULL) {
            cur->children[path] = new_node();
        }
        cur = cur->children[path];
    }
}

int max_eor(node *root, int eor) {
    node *cur = root;
    int max = 0, path, best;
    for (int move = 31; move >= 0; move--) {
        path = (eor >> move) & 1;
        best = move == 31 ? path : (path ^ 1);
        best = cur->children[best] == NULL ? (best ^ 1) : best;
        max = max << 1 | (path ^ best);
        cur = cur->children[best];
    }
    return max;
}

int main(void) {
    int n, *arr, ans = INT_MIN;
    scanf("%d", &n);
    arr = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    int eor = 0;
    node *root = new_node();
    insert(root, 0);
    for (int i = 0; i < n; i++) {
        eor ^= arr[i];
        ans = MAX(ans, max_eor(root, eor));
        insert(root, eor);
    }
    printf("%d\n", ans);
    destroy_whole_path(root);
    free(arr);
    return 0;
}

发表于 2022-02-14 00:45:53 回复(0)
#include<iostream>
#include<vector>
using namespace std;

void add(int newNum);
int maxXor(int eorj);
int maxXorSubarray2(vector<int> &arr);

class Node {
	public:
		Node *nexts[2] = {NULL};
};

Node *head = new Node();

void add(int newNum) {
	Node *cur = head;
	for (int move = 31; move >= 0; move--) {
		int path = ((newNum >> move) & 1);
		cur->nexts[path] = cur->nexts[path] == NULL ? new Node() : cur->nexts[path];
		cur = cur->nexts[path];
	}
}

int maxXor(int eorj) {
	Node *cur = head;
	int res = 0;
	for (int move = 31; move >= 0; move--) {
		int path = (eorj >> move) & 1;
		int best = move == 31 ? path : (path ^ 1);
		best = cur->nexts[best] != NULL ? best : (best ^ 1);
		res |= (path ^ best) << move;
		cur = cur->nexts[best];
	}
	return res;
}

int maxXorSubarray2(vector<int> &arr) {
	if (arr.empty() || arr.size() == 0) {
		return 0;
	}
	int mx = INT32_MIN;
	int eor = 0;
	add(0);
	for (int j = 0; j < arr.size(); j++) {
		eor ^= arr[j];
		mx = max(mx, maxXor(eor));
		add(eor);
	}
	return mx;
}

int main() {
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int res = maxXorSubarray2(arr);
	cout << res << endl;
	return 0;
}

发表于 2020-09-09 13:58:54 回复(0)
牛客的输入格式总是这么魔性,这题用缓冲流就数组越界,用Scanner又很慢。整体思路就是用字典树存储数组的前缀异或和,在遍历求前缀和的过程中考虑以arr[i]结尾时能够得到的最大异或和。假设能够让你得到这个最大异或和的子数组以arr[s]开头,则我们就需要确定s的位置。根据异或的性质,数组0~i范围上的异或和异或上数组0~s-1范围上的异或和,就能得到s~i范围上的异或和。而在遍历到i时,前面的前缀异或和已经全部加入到了字典树中,所以我们只要找到某个字典树中已经存在的前缀异或和,它与当前的前缀异或和eor异或完之后可以得到最大值就行了。因此我们在寻找这个符合条件的前缀异或和时,有如下两个贪心的思想:
  1. 对于符号位,我们希望找到一个与当前异或和状态相同的前缀异或和,因为同状态异或得0,可以使异或结果变成正数;
  2. 对于非符号位,我们希望找到一个与当前异或和状态不同的前缀异或和,因为不同状态才能使得异或结果为1。
从高位开始往低位执行上面的贪心策略,直到遍历完整型的32位(因为尽可能让高位为1能够使得异或和更大)。
import java.util.Scanner;

class Node {
    public Node[] next = new Node[2];     // 每个节点表示整数的一个位,有0和1两个状态
}

class NumTrie {
    public Node head = new Node();
    public void add(int num) {
        Node cur = head;
        for(int move = 31; move >= 0; move--){
            int bit = (num >> move) & 1;    // 取出从右往左的第move位
            cur.next[bit] = cur.next[bit] == null? new Node(): cur.next[bit];
            cur = cur.next[bit];
        }
    }
    
    public int maxXOR(int num) {
        Node cur = head;
        int res = 0;
        for(int move = 31; move >= 0; move--){
            int bit = (num >> move) & 1;
            int expect = move == 31? bit: bit ^ 1;      // 当前位为符号位时,希望要走的路径与当前位相同
            expect = cur.next[expect] == null? expect ^ 1: expect;      // 期望路径不空才能走
            res |= (bit ^ expect) << move;     // 把res中这一位的状态改了
            cur = cur.next[expect];
        }
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = Integer.MIN_VALUE;
        int eor = 0;      // 前缀异或和
        NumTrie trie = new NumTrie();
        trie.add(0);
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            eor ^= arr[i];
            max = Math.max(max, trie.maxXOR(eor));     // 找到数组以arr[i]结尾时,最大的异或和
            trie.add(eor);
        }
        System.out.println(max);
    }
}

发表于 2021-12-07 13:16:39 回复(0)
这题不知道为什么,用BufferedReader 就会数组越界,有明白的告知一下
发表于 2020-04-03 22:05:07 回复(0)
这输入描述有问题吧 为啥我这里是n行输入表示数组。。。

发表于 2022-09-01 13:56:42 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

class Node {
    public Node[] nodes;

    public Node() {
        nodes = new Node[2];
    }
}

class PrefixTree {
    public Node head;

    public PrefixTree() {
        this.head = new Node();
    }

    public void add(int eor) {
        Node cur = head;
        for (int move = 31; move >= 0; move--) {
            int i = (eor >> move) & 1;
            if (null == cur.nodes[i]) {
                cur.nodes[i] = new Node();
                cur = cur.nodes[i];
            } else {
                cur = cur.nodes[i];
            }
        }
    }

    public int max(int eor) {
        int res = 0;
        Node cur = head;
        for (int move = 31; move >= 0; move--) {
            int i = (eor >> move) & 1;
            int best;
            if (move == 31) {
                best = i;
            } else {
                best = i ^ 1;
            }
            if (cur.nodes[best] == null) {
                best = best ^ 1;
                cur = cur.nodes[best];
            } else {
                cur = cur.nodes[best];
            }
            res |= best << move;
        }
        return res ^ eor;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(reader.readLine());
        }
        int eor = 0;
        PrefixTree tree = new PrefixTree();
        tree.add(0);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            eor = eor ^ arr[i];
            max = Math.max(max, tree.max(eor));
            tree.add(eor);
        }
        System.out.println(max);
    }
}

发表于 2022-06-11 15:10:09 回复(0)
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(getMaxSum(arr));
    }
    
    /*
    //O(N^2)
    public static int getSum(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;
        //eor[i]的含义为arr[0...i]的异或和,只遍历arr一遍就可以生成eor数组
        int[] eor = new int[arr.length];
        eor[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            eor[i] = eor[i-1] ^ arr[i];
        }
        int max = Integer.MIN_VALUE;
        //因为xor[0...j] = xor[0...i-1] ^ xor[i...j]
        //所以xor[i...j] = xor[0...i-1] ^ xor[0...j]
        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i <= j; i++) {
                max = Math.max(max, i == 0 ? eor[j] : eor[j]^eor[i-1]);
            }
        }
        return max;
    }*/
    
    //O(N)
    /*
    此方法最大的优势在于可以直接得到当以j为止结尾时xor[j]的最大值,
    即通过从二进制最高位开始,尽可能的让更高位异或后的结果变1,
    相当于每一位上找之前结果eor[0]...eor[j-1]在此位置上有没有异或的可能,
    如果没有就将就了,如果有,就把1安在当前二进制数位上,最终以O(1)的代价获得
    以j位置结尾的最大异或和,然后遍历n个数,比较以每个位置为结尾的最大异或和,得到结果
    */
    public static int getMaxSum (int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;
        int max = Integer.MIN_VALUE;
        int eor = 0;
        NumTrie trie = new NumTrie();
        //为了当最大子数组只有一个数本身时,得到正确结果
        trie.add(0);
        for (int j = 0; j < arr.length; j++) {
            //因为xor[0...j] = xor[0...i-1] ^ xor[i...j]
            //所以xor[i...j] = xor[0...i-1] ^ xor[0...j]
            eor ^= arr[j];
            max = Math.max(max, trie.maxXor(eor));
            trie.add(eor);
        }
        return max;
    }
}

//把上面方法中eor[0...i]转变成前缀树结构
//二进制只有两种形式,所以每个节点下面最多只有两个node
class Node {
    public Node[] nexts;
    public Node() {
        nexts = new Node[2];
    }
}

class NumTrie {
    public Node head = new Node();
    //把某个数字加入前缀树中
    //num是一个32位的整数,所以加入过程一共走32步
    public void add (int num) {
        Node cur = head;
        for (int move = 31; move >= 0; move--) {
            //从最高位到最低位获得每一位上的数
            int path = (num >> move) & 1;
            cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
            cur = cur.nexts[path];
        }
    }
    
    public int maxXor(int eorj) {
        Node cur = head;
        int res = 0;
        for (int move = 31; move >= 0; move--) {
            //从最高位到最低位获得每一位上的数
            int path = (eorj >> move) & 1;
            //最高位上我们为了保证结果最大,当选取正数
            //如果当前eor[j]为负,即最高位为1,那么我们要走的路径也要是1
            //反之如果eor[j]为负,便走0,
            //其他情况下尽可能走向相反的数,因为这样下来从高到低才有可能有更多的1
            int best = move == 31 ? path : (path ^ 1);
            best = cur.nexts[best] != null ? best : (best^1);
            //看当前能得到的结果最好是多少
            res |= (path ^ best) << move;
            cur = cur.nexts[best];
        }
        return res;
    }
}

发表于 2021-08-05 16:26:43 回复(0)
n^2也能过的吗
发表于 2020-05-02 20:20:54 回复(1)