양의 정수 배열 A가 있다고 가정하고 이제 A[i]는 i번째 관광지의 값을 나타내고 두 개의 관광지 i와 j는 거리 j - i를 갖습니다. 이제 한 쌍의 관광 명소의 점수(i
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
set ret :=0, maxVal :=0, set n :=A의 크기
-
0 ~ n – 1 범위의 i에 대해
-
ret :=ret의 최대값 및 (maxVal + A[i] – i)
-
maxVal :=(A[i] + i) 및 maxVal의 최대값
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxScoreSightseeingPair(vector<int>& A) { int ret = 0; int maxVal = 0; int n = A.size(); for(int i = 0; i < n; i++){ ret = max(ret, maxVal + A[i] - i); maxVal = max(A[i] + i, maxVal); } return ret; } }; main(){ vector<int> v1 = {8, 1, 5, 2, 6}; Solution ob; cout << (ob.maxScoreSightseeingPair(v1)); }
입력
[8,1,5,2,6]
출력
11