Best sightseeing pair

Array Dynamic Programming

62.7% acceptance

Feb 25, 2026

3283

You are given an integer array values where values[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j - i between them. The score of a pair (i < j) of sightseeing spots is values[i] + values[j] + i - j: the sum of the values of the sightseeing spots, minus the distance between them. Return the maximum score of a pair of sightseeing spots.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
    let mut best = values[0] + 0; // values[i] + i
    let mut ans = 0;
    for j in 1..values.len() {
      ans = ans.max(best + values[j] - j as i32);
      best = best.max(values[j] + j as i32);
    }
    ans
  }
}