Сложность: 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 {
func maxScoreSightseeingPair(_ values: [Int]) -> Int {
var max_score = 0
var max_i_plus_value = values[0]
for j in 1..<values.count {
max_score = max(max_score, max_i_plus_value + values[j] - j)
max_i_plus_value = max(max_i_plus_value, values[j] + j)
}
return max_score
}
}Ставь 👍 и забирай 📚 Базу знаний