Сложность: medium
Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.
Пример:
Input: values = [8,1,5,2,6]
Output: 11
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.
2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.
3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.
😎 Решение:
class Solution {
function maxScoreSightseeingPair($values) {
$maxScore = 0;
$maxIPlusValue = $values[0];
for ($j = 1; $j < count($values); $j++) {
$maxScore = max($maxScore, $maxIPlusValue + $values[$j] - $j);
$maxIPlusValue = max($maxIPlusValue, $values[$j] + $j);
}
return $maxScore;
}
}Ставь 👍 и забирай 📚 Базу знаний