Best Sightseeing Pair — LeetCode 1014 Python Solution
MediumArrayDynamic Programming
- Problem
- #1014
- Pattern
- Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the array \textit{values} |
| Space | O(1) auxiliary |
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1014. Best Sightseeing Pair is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1014. Best Sightseeing Pair?
- LeetCode 1014. Best Sightseeing Pair is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1014. Best Sightseeing Pair?
- The Python solution on this page runs in O(n), where n is the length of the array \textit{values}.
- What is the space complexity of LeetCode 1014. Best Sightseeing Pair?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1014. Best Sightseeing Pair cover?
- LeetCode 1014. Best Sightseeing Pair is tagged Array and Dynamic Programming on LeetCode.