Algorithm
Problem Name: 1014. Best Sightseeing Pair
Problem Link: https://leetcode.com/problems/best-sightseeing-pair/
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 * 1041 <= values[i] <= 1000
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const maxScoreSightseeingPair = function(A) {
let res = 0, cur = 0;
for (let a of A) {
res = Math.max(res, cur + a);
cur = Math.max(cur, a) - 1;
}
return res;
};
Input
values = [8,1,5,2,6]
Output
11
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxScoreSightseeingPair(self, A: List[int]) -> int:
pre, mx = 0, -float('inf')
for j, a in enumerate(A):
mx = max(mx, pre + a - j)
pre = max(pre, a + j)
return mx
Input
values = [8,1,5,2,6]
Output
11