You are given an integer array values where values[i] represents the value of the ith sightseeing spot.
- i번째 관광번지의 값을 나타내는 정수 배열 값이 주어짐
Two sightseeing spots i and j have a distance j - i between them.
- 두 관광 명소 i와 jtkdldpsms j-i 거리가 존재
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.
- 관광 명소 쌍의 점수는 values[i] + values[j] + i-j, 관광 명소 값의 합에서 . 두관광 명소 사이의 거리를 뺀 값
Return the maximum score of a pair of sightseeing spots.
- 관광 명소 쌍의 최대 점수를 반환
접근1. DP
각 요소 values[i]가 두 가지 방법으로 점수의 일부가 될 수 있음을 확인합니다.
왼쪽 요소로 점수에 values[i] + i를 더합니다.
오른쪽 요소로 : 점수에 values[i]-i를 더합니다.
이제 j위치에 오른쪽 요소를 고정합니다
최상의 점수를 얻으려면 i위치(i<j)에서 values[i]+i에 대해 가장 큰 값을 제공하는 왼쪽 요소를 찾아야 합니다.
그러기 위해선 j까지의 모든 인덱스에 대해 이 값을 계산하여 가장 높은 값을 구해야합니다.
이제 인덱스 j+1이 인덱스 j보다 더 나은 오른쪽 지점인지 확인해야 합니다.
어떻게 해야 할까요?
배열을 다시 살펴보고 모든 인덱스 0, 1, ..., j에 대해. 왼쪽 점수를 비교해야 할지, 아니면 더나은 전략이 있을까요?
처음부터 각 새j에 대한 최상의 값[i]+i를 다시 계산하는 대신,
배열을 진행하면서 마주친 최상의 값[i]+i를 추적할 수 있습니다.
이런 식으로, 매번 전체 배열을 다시 검토하는 대신 이전 단계에서 계산된 결과를 재사용할 수 있습니다. 이전 단계의 결과를 재사용할 수 있다는 것을 인식하면 문제의 겹치는 상태를 알 수 있고 동적 프로그래밍 접근 방식에 도달하는데 도움이 됩니다.
동적 프로그래밍 : 동적 프로그래밍에 대한 보다 포괄적인 이해를 위해 동적 프로그래밍 탐색 카드를 확인하세요.
이 리소스는 동적 프로그래밍에 대한 심층적인 살펴보기를 제공하며, 다양한 문제를 통해 핵심 개념과 응용 프로그램을 설명하여 패턴에 대한 이해를 강화합니다.
알고리즘
- n 크기의 배열 maxLeftScore를 초기화하여 . 각인덱스까지의 최대 좌측 점수를 저장합니다.
- 첫 번째 인덱스의 좌측 점수는 단순히 첫 번째 요소의 값이므로 maxLeftScore[0]을 values[0]으로 설정합니다.
- 관광 쌍의 최대 점수를 추적하려면 maxScore를 0으로 초기화합니다.
- 인덱스 1에서 n - 1까지 배열을 반복합니다.
- 관광 쌍의 현재 우측 점수를 values[i] - i로 계산합니다.
- 지금까지의 가장 좋은 좌측 점수(maxLeftScore[i - 1])와 현재 우측 점수를 결합하여 maxScore를 업데이트합니다.
- 현재 좌측 점수를 values[i] + i로 계산합니다.
- maxLeftScore[i]를 maxLeftScore[i - 1]과 currentLeftScore의 최대값으로 업데이트하여 현재 인덱스까지의 가장 좋은 좌측 점수를 저장합니다.
- 반복을 완료한 후 최대 관광 쌍 점수가 포함된 maxScore를 반환합니다.
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int n = values.length;
// Initialize an array to store the maximum left scores up to each index.
int[] maxLeftScore = new int[n];
// The left score at the first index is just the value of the first element.
maxLeftScore[0] = values[0];
int maxScore = 0;
for (int i = 1; i < n; i++) {
int currentRightScore = values[i] - i;
// Update the maximum score by combining the best left score so far with the current right score.
maxScore = Math.max(
maxScore,
maxLeftScore[i - 1] + currentRightScore
);
int currentLeftScore = values[i] + i;
// Update the maximum left score up to the current index.
maxLeftScore[i] = Math.max(maxLeftScore[i - 1], currentLeftScore);
}
return maxScore;
}
}복잡도 분석
- n을 배열의 길이로 둘 때
시간 복잡도 : O(n)
배열을 한 번 반복하고 각 반복에서 상수 시간 연산을 수행합니다. 따라서 알고리즘의 시간 복잡도는 O(n)입니다.
공간 복잡도: O(n)
각 인덱스까지의 최대 좌측 점수를 저장하기 위해 크기가 n인 배열 maxLeftScore를 만듭니다.
이것이 알고리즘에 O(n)의 추가 공간이 필요한 이유입니다.
