[LeetCode] 1014. Best Sightseeing Pair

https://leetcode.com/problems/best-sightseeing-pair/description/

leetcode - Best Sightseeing Pair

문제 유형: 그리디, 다이나믹 프로그래밍

문제 난이도: Medium

 

문제

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.

 

두 위치의 경치 점수는 두 value의 합에 거리를 뺀 값이다.

가장 큰 경치 점수를 구하시오.

 

풀이

각 j에서의 가장 큰 i를 찾아서 최대값을 구해 업데이트 하면 된다.

values[i] + values[j] + i - j를 values[i] + i와 values[j] - j 두 부분으로 나누면, 구하기 쉬워질 것이다.

i에 대한 쌍은 j보다 작은 인덱스에서 가장 큰 i를 구하면 되고, j는 한 칸씩 밀면서 구해보면 된다.

 

 

코드

C++

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int n = values.size();
        vector<int> lefts(n);
        lefts[0] = values[0];
        int ans = 0;
        for(int i = 1; i < n; ++i) {
            int currRight = values[i] - i;
            ans = max(ans, lefts[i-1] + currRight);

            lefts[i] = max(lefts[i-1], values[i] + i);
        }

        return ans;
    }
};