Сложность: 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 как максимальную оценку пары достопримечательностей.
😎 Решение:
public class Solution {
public int maxScoreSightseeingPair(int[] values) {
int maxScore = 0;
int maxIPlusValue = values[0];
for (int j = 1; j < values.length; j++) {
maxScore = Math.max(maxScore, maxIPlusValue + values[j] - j);
maxIPlusValue = Math.max(maxIPlusValue, values[j] + j);
}
return maxScore;
}
}Ставь 👍 и забирай 📚 Базу знаний