LeetCode 1014: Best Sightseeing Pair Solution

Master LeetCode problem 1014 (Best Sightseeing Pair), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1014. Best Sightseeing Pair

Medium

Array Dynamic Programming

Problem Explanation

Explanation

To find the maximum score of a pair of sightseeing spots, we need to maximize the expression values[i] + values[j] + i - j. We can rewrite this expression as (values[i] + i) + (values[j] - j) for a pair (i, j). The first part values[i] + i can be precomputed for each index i and stored in an array. Then, for each index j, we can find the maximum score by adding values[j] - j to the maximum value of values[i] + i seen so far.

Solution Code

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int maxPrev = values[0] + 0;
        
        for (int j = 1; j < values.length; j++) {
            maxScore = Math.max(maxScore, maxPrev + values[j] - j);
            maxPrev = Math.max(maxPrev, values[j] + j);
        }
        
        return maxScore;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1014 (Best Sightseeing Pair)?

This page provides optimized solutions for LeetCode problem 1014 (Best Sightseeing Pair) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1014 (Best Sightseeing Pair)?

The time complexity for LeetCode 1014 (Best Sightseeing Pair) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1014 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1014 in Java, C++, or Python.

Back to LeetCode Solutions