Сложность: easy
Вам дан целочисленный массив 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 {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int max_score = 0;
int max_i_plus_value = values[0];
for (int j = 1; j < values.size(); ++j) {
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;
}
};Ставь 👍 и забирай 📚 Базу знаний