有一个长度为$n$的数组$a$，数组中每个元素都是整数，取值范围是$[0, 10^{9}]$。设$b$是$a$的一个子数组。

定义$b$的异或和为$b$中所有元素的异或运算结果，即$f(b) = b[0] \oplus b[1] \oplus \cdots \oplus b[k]$。

定义$b$的GCD为$b$中所有元素的最大公约数，即$g(b) = GCD(b[0], b[1], \cdots, b[k])$。

你可以从$a$中选择任意一个子数组$b$，满足$f(b) \cdot g(b)$尽可能大吗？请你算一算这个最大值。

这题其实用了一个结论：

$$ \boxed{\max { f(b) \cdot g(b) } = (\max a_i)^2} $$

也就是说，所求的最大值 就是数组最大元素的平方，与数组的元素分布无关。我们来证明一下：

证明

对于任意子数组 $b$，设其最大元素为 $M$，则有重要结论： $$ f(b) \triangleq b_0 \oplus b_1 \oplus \cdots \oplus b_k < 2M $$

即一个数组的异或和严格小于最大元素的2倍。

这部分的证明：

• 设 $M$ 的二进制最高位为第 $k$ 位（即 $M \in [2^k, 2^{k+1})$）。
• 异或操作的每一位结果独立，最高位为1的次数若为奇数次，则结果最高位为1；否则为0。
• 无论奇偶，异或和的最高位不可能超过 $k+1$ 位，即严格小于 $2^{k+1} \leq 2M$。

我们再分析 $g(b)$ 的上界。子数组的 GCD 满足：

• 如果$b$的元素都相同，则$g(b) = M$。
• 如果$b$的元素不全相同，则 $\displaystyle g(b) \leqslant \frac{M}{2}$。

这个也很好证明。如果全相同，显然成立。如果不全相同，由于一个数的最大因数（除这个数本身）不大于这个数的一半，所以数组的最大公约数不大于最大元素的一半。

那么，现在有两种情形：

• 如果子数组的元素都相同，则：
  • 当$n$为偶数时，$f(b) = 0$，$g(b) = M$，$f(b) \cdot g(b) = 0$。
  • 当$n$为奇数时，$f(b) = M$，$g(b) = M$，$f(b) \cdot g(b) = M^2$。
• 如果子数组的元素不全相同，则：
  • $f(b) < 2M$，$\displaystyle g(b) \leqslant \frac{M}{2}$，$f(b) \cdot g(b) < M^2$。

这就证明了： $$ \max { f(b) \cdot g(b) } = M^2 $$ 只需取子数组为单元素 $M$，即可达到理论最大值。

用到的结论

• 一个正整数数组的异或和严格小于最大元素的2倍。
• 一个正整数数组的最大公约数不大于最大元素的一半。

代码

1public class Solution {
2    public static int maxXorGcd(int[] a) {
3        int max = 0;
4        for (int i = 0; i < a.length; i++) {
5            max = Math.max(max, a[i]);
6        }
7        return max * max;
8    }
9}