Максимизируйте значение выражения [ij – K.(Ai | Aj)] по всем парам (i, j) в заданном массиве

Дан массив A [] длины N и целое число K. Задача состоит в том, чтобы максимизировать значение выражения [ij – K.(A _i | A _j )] по всем парам (i, j) в заданном массиве, где ( 1 ≤ i < j ≤ N) и | обозначает побитовый оператор ИЛИ .

Примеры:

Input: A[] = {5, 20, 1, 0, 8, 11}, K = 10
Output: 2
Explanation: The maximum value of the expression f(i, j) = i.j – K.(A[i] | A[j]) can be found for below pair:
f(3, 4) = 3.4 – 10.(1 | 0) = 2

Input: A[] = {1, 5, 6, 7, 8, 19}, K = 3
Output: -9

Подход: Необходимо сделать следующие замечания:

Let f(i, j) = i.j – K.(A_i | A_j). 

=> Notice that for f(i, j) to be maximum, i.j should be maximum and K.(A_i | A_j) should be minimum.
=> Thus, in the best case, f(i, j) will be maximum if 
      => K.(A_i | A_j) is equal to 0
      => i = (N-1) and j = N.
=> So, the maximum value of the expression can be f(i, j) = (N-1)*N.

=> Also, the minimum value will be obtained by subtracting the maximum value of K.(A_i | A_j) from (N-1)*N. 

=> It is known that 
a | b < 2*max(a, b) where | is the bitwise OR operator

Из приведенного выше свойства и заданных ограничений можно сделать вывод:

• Максимальное значение (A _i | A _j ) может быть 2*N . потому что (0 ≤ A _i ≤ N)
• Максимальное значение K может быть 100, потому что (1 ≤ K ≤ min(N, 100)) .
• Итак, минимальное значение f(i, j) будет:

f(i, j) = (N-1)*N – K*(A_i | Aj)
       = (N-1)*N – 100*2*N
       = N*(N – 201)

• Легко заметить, что результирующий ответ всегда будет лежать между:

N*(N-201) <= ans <= (N-1)*N

• Также обратите внимание, что для i = N – 201 и j = N
  • максимальное значение f(i, j) будет N*(N – 201) ,
  • что, в свою очередь, является минимальным значением f(i, j) для i = N – 1 и j = N .
  • Таким образом, максимальное значение выражения должно быть проверено от i = N – 201 до i = N и от j = i+1 до j = N.

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

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