Следующая наша задача - 1014. Best Sightseeing Pair.
Описание задачи 📝
Дано: массив values, где
values[i] — это ценность туристической достопримечательности,j-i — расстояние между двумя достопримечательностями i и j.
Требуется: найти пару достопримечательностей (i < j) с максимальной совместной ценностью по формуле:
score = values[i] + values[j] + i − j
Идея 💡
Основная задача заключается в оптимизации вычислений. Если переписать формулу как:
score = (values[i] + i) + (values[j] − j),
то видно, что для эффективного решения нужно поддерживать максимум для values[j]−j во время итерации.
Это позволяет избежать вложенных циклов и сократить сложность до O(n).
Детали подхода 🛠️
- Используем обратный обход массива с помощью
.enumerate().rev().
- На каждой итерации:
- Вычисляем текущую наилучшую ценность:
score = values[i] + i + max_right,
где max_right — лучшее значение values[j] − j, найденное до текущего момента.
- Обновляем
max_right как максимум из текущего значения values[i] − i и предыдущего max_right.
- Для вычислений используем:
.map() для расчёта текущего результата..max() для нахождения наибольшего значения.
Асимптотика ⏳
- Время:
O(n), так как массив обходится один раз.
- Память:
O(1), так как не используются дополнительные структуры данных, кроме пары скалярных переменных.
Исходный код 📜
impl Solution {
pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
if values.len() < 2 {
panic!("Input must have at least two elements"); // Handle invalid input explicitly
}
// Iterate in reverse to calculate max scores
let mut max_right = i32::MIN; // Best "values[j] - j" seen so far
values.into_iter().enumerate().rev()
.map(|(i, value)| {
// Calculate the score for the current pair (i, j)
let score = value + i as i32 + max_right;
// Update max_right for the next iteration
max_right = max_right.max(value - i as i32);
score
}).max().unwrap() // Return the maximum score
}
}