Skip to content

1014. Best Sightseeing Pair

SourceWeekly Contest 129 Q3DifficultyMediumRating1730

Description

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.

 

Example 1:

Input: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

Example 2:

Input: values = [1,2]
Output: 2

 

Constraints:

  • 2 <= values.length <= 5 * 104
  • 1 <= values[i] <= 1000

Solutions

Solution 1: Enumeration

Thinking

Evaluating \(\textit{values}[i]+\textit{values}[j]+i-j\) for every \(i<j\) is quadratic. Rewriting it as \((\textit{values}[i]+i)+(\textit{values}[j]-j)\) shows that a fixed \(j\) only needs the best \(\textit{values}[i]+i\) to its left.

Scanning \(j\) from left to right, one variable stores that prefix maximum, giving the best pair at \(j\) in constant time before we fold in \(\textit{values}[j]+j\).

Each index is used once as a right endpoint and once as a left candidate, so the scan is linear.

We can enumerate \(j\) from left to right while maintaining the maximum value of \(\textit{values}[i] + i\) for elements to the left of \(j\), denoted as \(mx\). For each \(j\), the maximum score is \(mx + \textit{values}[j] - j\). The answer is the maximum of these maximum scores for all positions.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{values}\).

1
2
3
4
5
6
7
class Solution:
    def maxScoreSightseeingPair(self, values: list[int]) -> int:
        ans = mx = 0
        for j, x in enumerate(values):
            ans = max(ans, mx + x - j)
            mx = max(mx, x + j)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, mx = 0;
        for (int j = 0; j < values.length; ++j) {
            ans = Math.max(ans, mx + values[j] - j);
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0, mx = 0;
        for (int j = 0; j < values.size(); ++j) {
            ans = max(ans, mx + values[j] - j);
            mx = max(mx, values[j] + j);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
func maxScoreSightseeingPair(values []int) (ans int) {
    mx := 0
    for j, x := range values {
        ans = max(ans, mx+x-j)
        mx = max(mx, x+j)
    }
    return
}
1
2
3
4
5
6
7
8
function maxScoreSightseeingPair(values: number[]): number {
    let [ans, mx] = [0, 0];
    for (let j = 0; j < values.length; ++j) {
        ans = Math.max(ans, mx + values[j] - j);
        mx = Math.max(mx, values[j] + j);
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut mx = 0;
        for (j, &x) in values.iter().enumerate() {
            ans = ans.max(mx + x - j as i32);
            mx = mx.max(x + j as i32);
        }
        ans
    }
}

Comments