aboutsummaryrefslogtreecommitdiff
path: root/best_sightseeing_pair.py
blob: 7fecb669f22f90e9d607fa68a7671f450c358830 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 1014. Best Sightseeing Pair

"""
you are given an integer array 'values' where 'values[i]' represents the
value of the i'th 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.
"""


class Solution(object):
    def maxScoreSightseeingPair(self, values):
        """
        :type values: List[int]
        :rtype: int
        """
        ans, curr = 0, 0
        for i in values:
            ans = max(ans, curr + i)
            curr = max(curr, i) - 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxScoreSightseeingPair(values=[8, 1, 5, 2, 6]))
    print(obj.maxScoreSightseeingPair(values=[1, 2]))