Максимальное значение arr[i] + arr[j] + i – j для любой пары массива

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти максимальное значение (arr[i] + arr[j] + i − j) для любой возможной пары (i, j) данного массива.

Примеры:

Input: arr[] = {1, 9, 3, 6, 5}
Output: 13
Explanation:
The pair of the array having the maximum value of (arr[i] + arr[j] + i − j) is (1, 3). The value is (arr[1] + arr[3] + 1 – 3) = (9 + 6 + 1 – 3) = 13. 

Input: arr[] = {6, 2, 5, 6}
Output: 10

Наивный подход: самый простой подход к решению данной проблемы — сгенерировать все возможные пары (i, j) заданного массива и найти максимальное значение выражения среди всех возможных пар.

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, разбив выражение (arr[i] + arr[j] + i – j) на две части: (arr[i] + i) и (arr[j] – j) а затем максимизируйте сумму максимального значения (arr[i] + i) со всеми возможными значениями (arr[i] – i) . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте две переменные: res со значением 0 для хранения требуемой суммы и maxValue с arr[0] для отслеживания максимального значения (arr[i] + i) .
• Пройдите по заданному массиву arr[] в диапазоне [1, N – 1], используя переменную i , и выполните следующие шаги:
  • Сохраните значение выражения в X как (maxValue + arr[i] – i) .
  • Если значение X больше, чем res , то обновите значение res до X.
  • Если значение arr[i] + i больше, чем maxValue , обновите maxValue до (arr[i] + i) .
• После выполнения вышеуказанных шагов выведите в качестве результата значение res .

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

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