Best Sightseeing Pair

Leetcode Problem 1014: Best Sightseeing Pair

Problem Summary

You are given an array values where values[i] is the score of the i-th sightseeing spot. The score of a pair of spots at indices i < j is values[i] + values[j] + i - j (the sum of their scores minus the distance between them). Return the maximum score of any such pair.

Constraints:

• The array has between 2 and 50,000 elements.
• Each value is a positive integer between 1 and 1,000.

Techniques

• Array
• Dynamic Programming

Solution

function maxScoreSightseeingPair(values: number[]): number {
    let maxElementIPlusIndexI = 0
    let bestSightseeingPair = 0

    for (let j = 1, i = 0; j < values.length; j++, i++) {
        maxElementIPlusIndexI = Math.max(maxElementIPlusIndexI, values[i] + i)
        bestSightseeingPair = Math.max(bestSightseeingPair, maxElementIPlusIndexI + values[j] - j)
    }

    return bestSightseeingPair
};

console.log(maxScoreSightseeingPair([5,1,8,2,6]))