Max XOR sub sequence | Algorithm Notes

Max XOR sub sequence | Algorithm Notes
Given an array contains only positive integers, find a sub sequence that after reduce all elements by XOR operator, the result is the largest. Return the largest number.
O(NlogN)

    public static int findMaxTrie(int[] array) {
        Trie trie = new Trie();
        trie.add(0);
        int max = 0;
        int cur = 0;
        for (int i = 0; i < array.length; i++) {
            cur ^= array[i];
            TrieNode p = trie.root;
            int x = 0;
            for (int j = 30; j >= 0; j--) {
                if (((cur >> j) & 1) == 1) {
                    if (p.zeroChild != null) {
                        p = p.zeroChild;
                    } else {
                        x |= (1 << j);
                        p = p.oneChild;
                    }
                } else {
                    if (p.oneChild != null) {
                        x |= (1 << j);
                        p = p.oneChild;
                    } else {
                        p = p.zeroChild;
                    }
                }
            }
            max = Math.max(max, x ^ cur);
            trie.add(cur);
        }
        return max;
    }

Brute force - O(N^2)

    public int findMaxBruteForce(int[] array) {
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            int m = 0;
            for (int j = i; j < array.length; j++) {
                m ^= array[j];
                max = Math.max(max, m);
            }
        }
        return max;
    }

Read full article from Max XOR sub sequence | Algorithm Notes