C++ এ সেরা দর্শনীয় জুটি

ধরুন আমাদের কাছে ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে রয়েছে, এখন A[i] i-th দর্শনীয় স্থানের মানকে প্রতিনিধিত্ব করে, এবং দুটি দর্শনীয় স্থান i এবং j-এর দূরত্ব j - i। এখন দর্শনীয় স্থানগুলির একটি জোড়ার (i

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সেট ret :=0, maxVal :=0, সেট 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