C++で最高の観光ペア

正の整数の配列Aがあり、A [i]がi番目の観光スポットの値を表し、2つの観光スポット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の最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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