Best Sightseeing Pair
Real-world version: Best Pair of Lookout BoardsThe statement here is our own: the same inputs, outputs and technique.
Interpretive boards stand one step apart along a ridge trail, numbered 0 upward. Board i carries a review score values[i], which may be negative when visitors disliked it.
A guide picks an ordered pair of boards: an earlier board i and a later board j, with i strictly before j. The pair is rated by adding the two review scores together and then taking away the number of steps walked between the two boards, which is j - i.
Return the highest rating any such pair reaches.
Examples
Example 1
- Input
- values = [5, 4, 4, 4, 4, 100]
- Output
- 103
Pairing board 4 with board 5 adds 4 and 100 and takes away the single step between them, giving 103. No other pair reaches that.
Example 2
- Input
- values = [-3, -4]
- Output
- -8
Only one pair exists. Adding -3 and -4 gives -7, and one step is walked, so the rating is -8.
Example 3
- Input
- values = [1, -500, 1000]
- Output
- 999
Boards 0 and 2 add to 1001 and are two steps apart, for 999. Boards 1 and 2 add to 500 and are one step apart, for 499, and boards 0 and 1 rate -500.
Constraints
- 2 <= values.length <= 5 * 10^4
- -1000 <= values[i] <= 1000
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def max_score_sightseeing_pair(values: list[int]) -> int:public int maxScoreSightseeingPair(int[] values)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's