competitive-programming2022년 2월 17일1분 분량

[LeetCode] 1014. Best Sightseeing Pair 풀이

수정일: 2022년 2월 17일

MathDynamic programming

지원 언어:enko

#Problem

1014. Best Sightseeing Pair

#Approach

score 값이 두 부분으로 이루어져 있음에 주목합니다.
값들을 순회하면서 best left pair의 인덱스를 찾고, 이를 maxLeftScore에 캐싱합니다.

i: left pair 후보의 인덱스.
j: right pair 후보의 인덱스.

j를 이동할 때마다,

인덱스 j-1이 새로운 i가 될 수 있는가? 그렇다면 maxLeftScore를 갱신합니다.
max(maxScore, score(i,j))로 maxScore 값을 갱신합니다.

#Code

typedef vector<int> vi;

class Solution {
public:
    static inline int maxScoreSightseeingPair(vi &values) {
        int n= values.size(), maxLeftScore= 0, maxScore= 0;
        for (int j=1; j < n; ++j) {
            maxLeftScore= max(maxLeftScore, values[j-1]+j-1);
            maxScore= max(maxScore, values[j]-j+maxLeftScore);
        }
        return maxScore;
    }
};

#Complexity

Time: $O(N)$
Space: $O(1)$