Best Sightseeing Pair LeetCode solution in Python

1
class Solution:
2
    """
3
    Approach:
4
    O(n^2) is very straight forward
5
    For all the possible pairs
6
    for i in range(n)
7
      for j in range(i+1, n)
8
         value[i] = max(value[i], value[i] + value[j] + i - j`)
9

10
    we can do this problem in O(n) as well
11
    values = [8, 1, 5, 2, 6]
12
    max_val = [0, 0, 0, 0, 0]
13
    max_val[i] = max(max_val[i-1]-1, values[i-1]-1)
14
    we have to do it once from left side and then from right side
15
    """
16

17
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
18
        left_max_vals = [float("-inf") for _ in range(len(values))]
19
        right_max_vals = [float("-inf") for _ in range(len(values))]
20

21
        for i in range(1, len(values)):
22
            left_max_vals[i] = max(left_max_vals[i - 1] - 1, values[i - 1] - 1)
23

24
        for i in range(len(values) - 2, -1, -1):
25
            right_max_vals[i] = max(right_max_vals[i + 1] - 1, values[i + 1] - 1)
26

27
        max_pair = float("-inf")
28
        for i in range(len(values)):
29
            max_pair = max(
30
                max_pair, values[i] + max(left_max_vals[i], right_max_vals[i])
31
            )
32
        return max_pair