Максимальная сумма двух элементов в массиве минус расстояние между ними

Question

Я пытаюсь найти максимальную сумму двух элементов в массиве минус расстояние между ними. В частности, я пытаюсь вычислить max {a [i] + a [j] - | ij | } Я сейчас застрял. Я очевидно рассмотрел наивный подход (O (n ^ 2)). Тем не менее, я уверен, что есть лучший, более эффективный подход (O (nlogn)) или даже O (n). Может кто-нибудь, пожалуйста, помогите мне, как подойти к проблеме. Я был бы признателен, если бы кто-нибудь дал намек или простую идею, чтобы начать с чего-то. Сортировка массива в первую очередь? Может быть, с использованием динамического c подхода к программированию?

Редактировать: Я думаю, что нашел решение O (n) Давайте предположим, что наша максимальная сумма получается из a [i] и a [j], a [i ] вносит в эту сумму: a [i] + i. a [j] вносит вклад в эту сумму с помощью [j] -j. (Поскольку наша сумма - это [i] + a [j] - | ji | = a [i] + a [j] + ij.) Подход: для удобства мы вычисляем матрицы A_plus_index = a [i] + i и A_minus_index = а [I] -i. Затем мы используем два вспомогательных массива: i) первый имеет для каждого i максимальное значение массива A_plus_index, учитывающее только элементы от 0 до i. ii) второе имеет для каждого i максимальное значение массива A_minus_index, учитывающее только элементы от N до i, где N - длина массива a. Теперь мы просматриваем массивы один раз и находим max: A_plus_index [i] + A_minus_index [i + 1]. Общая сложность O (n).

Answer 1

@ JeffersonWhite ваша идея работает, и вы можете опубликовать ее в качестве ответа и принять ее.

Но я собираюсь немного улучшить вашу идею:

Вы можете построить только одну массив вместо 2, который на данный момент содержит максимум A[j] - j для каждого j от N-1 до 1.

, а затем каждый раз пересекает массив вперед, вычисляя max( A[i] + i + max_so_far-_reverse[i+1])

//Building the reverse array
max_so_far_reverse = array of length N
max_reverse = A[N-1]-(N-1)
max_so_far_reverse[N-1] = max_reverse
for j = N-2 to 1:
   max_reverse = max(max_reverse, A[j]-j)
   max_so_far_reverse[j] = max_reverse

//Computing maximum value by traversing forward
max = 0
for i = 0 to N-2:
    max = max(max, A[i] + i + max_so_far_reverse[i+1])

return max