สุดยอดสถานที่ท่องเที่ยวใน C++

สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็มบวก ตอนนี้ A[i] แทนค่าของจุดท่องเที่ยวที่ i และจุดท่องเที่ยวสองแห่งที่ i และ j มีระยะทาง j - i ตอนนี้คะแนนของสถานที่ท่องเที่ยวหนึ่งคู่ (i

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• Set ret :=0, maxVal :=0, set n :=ขนาดของ A

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • 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