C++ 최고의 관광 쌍

양의 정수 배열 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