Разделить массив на подмассивы с максимальным побитовым XOR их соответствующих значений побитового ИЛИ

Учитывая массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти максимальное побитовое XOR для побитового ИЛИ каждого подмассива после разделения массива на подмассивы (возможные нулевые подмассивы).

Примеры:

Input: arr[] = {1, 5, 7}, N = 3
Output: 7
Explanation:
The given array can be expressed as the 1 subarray i.e., {1, 5, 7}.
The Bitwise XOR of the Bitwise OR of the formed subarray is 7, which is the maximum possible value.

Input: arr[] = {1, 2}, N = 2
Output: 3

Наивный подход: Самый простой подход к решению данной выше задачи состоит в том, чтобы сгенерировать все возможные комбинации разбиения подмассивов с помощью рекурсии и при каждом рекурсивном вызове найти максимальное значение побитового XOR или побитового ИЛИ всех возможных сформированных подмассивов и вывести его на печать.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(2 ^N )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать, наблюдая взаимосвязь между побитовым исключающим ИЛИ и побитовым ИЛИ, т. е. значение побитового исключающего ИЛИ для N элементов не превышает значения побитового ИЛИ для N элементов. Поэтому, чтобы найти максимальное значение, идея состоит в том, чтобы разбить группу только на 1 группу всего массива.

Следовательно, выведите значение побитового ИЛИ элементов массива arr[] как результирующее максимальное значение.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)