C ++最佳观光对

假设我们有一个正整数数组A，现在A [i]表示第i个景点的值，两个景点i和j的距离为j-i。现在，一对观光景点（i <j）的得分遵循以下公式（A [i] + A [j] + i-j）：我们必须找到一对观光景点的最大得分。因此，如果输入类似于[8,1,5,2,6]，则输出将为11，因为i = 0，j = 2，所以A [0] + A [2] + 0 – 2的值= 8 + 5 + 0 – 2 = 11。

为了解决这个问题，我们将遵循以下步骤-

• 设置ret：= 0，maxVal：= 0，设置n：= A的大小

• 对于i，范围为0至n – 1

• 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