[코테연습] 1014. Best Sightseeing Pair

문제 타입

• Dynamic Programming 또는 Greedy Algorithm
• 배열 내에서 특정 규칙을 만족하는 두 요소의 최대값을 구하는 문제

---

문제 분석

• 문제 요구사항
  • 배열 values에서 두 인덱스 i와 j (i < j)를 골라 values[i] + values[j] + i - j 값을 최대화하라.
• 주요 관찰
  • values[i] + values[j] + i - j는 values[i] + i + (values[j] - j)로 재구성 가능.
  • 이를 통해 values[i] + i와 values[j] - j의 최대값 문제로 변환할 수 있음.
• 최적화 아이디어
  • values[i] + i의 최대값을 계산하면서 순회를 진행하여, 현재 인덱스 j에서 최대값을 업데이트한다.

---

문제 풀이

• 접근 방법
  1. 배열의 첫 번째 요소를 기준으로 초기 maxI (즉, values[i] + i) 값을 설정.
  2. 배열의 두 번째 요소부터 순회하며:
     • maxScore를 maxI + values[j] - j로 계산 및 갱신.
     • maxI를 values[j] + j와 비교하여 갱신.

 

> java

 

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int maxI = values[0]; // 초기값: 첫 번째 값 + 인덱스 0
        
        for (int j = 1; j < values.length; j++) {
            // i와 j가 다른 조건에서의 최대 점수 계산
            maxScore = Math.max(maxScore, maxI + values[j] - j);
            
            // maxI를 업데이트 (values[i] + i의 최대값)
            maxI = Math.max(maxI, values[j] + j);
        }
        
        return maxScore;
    }
}