Best Sightseeing Pair

개인적으로 되게 어렵다고 느꼈던 문제였다. 아무리 봐도 패턴을 찾기가 힘들었고 전에 풀었던 DP문제랑은 다르게 엄청 색다로운 패턴으로 매번 다른 값을 비교한다고 생각해서 정말 어떻게 해야할지 감도 안왔어서 답을 참고했다. 문제는 답을 보고도 뭔지 몰라서 한참 어지러웠다.. 결국 노트에 계속 비교공식을 써가면서 봤더니 중복되는 구간을 찾았고 이것을 DP로 어떻게 활용해야 하는지 느꼈다.

내가 100번 설명하는것보다 디스커션에 쓰여있는걸 참고했는데 훨씬 이해가 잘됐다. Max값을 두번쓰면서 최대값을 유지하는게 핵심이었다. 결국 문제를 계속해서 작성하다보면 반복 구간이 나오는데 이 구간을 DP로 만드는게 가장 중요한 연습일거같다.

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
         int[] dp = new int[values.length]; 
         dp[0] = 0; 
         int answer = 0; 

         for(int i = 1; i < values.length; i++){
            dp[i] = Math.max(dp[i-1],values[i-1] + i -1); 
            answer = Math.max(answer,dp[i] + values[i] - i); 
         }



         return answer; 
    }
}

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& val) {
        int n = val.size();
        vector<int> vec(n,0);
        vec[1] = val[0]+val[1]-1;
        int ans = vec[1];
        for(int i=2;i<n;i++){
            vec[i] = max(vec[i-1]-val[i-1]+val[i]-1,val[i-1]+val[i]-1);
            ans = max(vec[i],ans);
        }
        return ans;
    }
};