Leetcode 1014. Best Sightseeing Pair

문제

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.

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.

• 정수로 이루어진 배열이 주어진다.
• 이 정수들의 쌍은 점수를 가진다.
  • 쌍에 포함된 값의 합 - 두 쌍의 거리
• 최대로 얻을수 있는 위 점수의 값을 리턴하시오

예시

[8,1,5,2,6]

• 0번 index의 8과 2번 index의 5가 쌍을 이룬다.
• 8 + 5 - 2 = 11 이 최대
• 정답 : 11

제한

• 2 <= values.length <= 5 * 10^4
• 1 <= values[i] <= 1000

n값의 제한으로 인해 O(N^2) 이상의 알고리즘은 TLE가 된다.

풀이

• 풀이방법은 다음과 같다
• 쌍에 대해 뒤에 나오는것을 기준으로 하여 앞의 값을 찾는다.
• [8, 1, 2, 4] 가 있을경우 1부터 탐색
  • 근데 8 과 1은 간격이 1이 있다.
  • 이걸 고려해 8에 미리 1을 빼놓는다.
  • 7, 1 pair 가 되고 점수는 8이 된다.
• 다음 값인 2가 끝에 온다고 가정할때, 이전에 있던 값 1에 1을 빼서 0으로 만들고 이전의 최대값인 7도 1을뺀다
• 이 6과 0을 비교해 큰 값을 선택해 앞부분 값으로 설정한다.
• 이것을 끝까지 반복하면 완료!

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        pre_max = values[0] - 1

        ans = 0

        for i in range(1, len(values)):
        	# 정답 최댓값 찾기
            ans = max(ans, pre_max + values[i])

			# 이전 최대값에 1뺀것과 새로운 값에 1 뺀것 비교해서 올리기
            pre_max -= 1
            pre_max = max(pre_max, values[i] - 1)

        return ans