C++ में बेस्ट साइटसीइंग पेयर (Best Sightseeing Pair)

मान लीजिए हमारे पास धनात्मक पूर्णांकों का एक ऐरे 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।

समाधान दृष्टिकोण

1. ret := 0, maxVal := 0, n := A का आकार सेट करें

2. i को 0 से n-1 तक लूप चलाएं

3. ret := max(ret, maxVal + A[i] - i) अपडेट करें

4. maxVal := max(A[i] + i, maxVal) अपडेट करें

5. ret लौटाएं

C++ कार्यान्वयन

#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; 
    } 
}; 

int main(){ 
    vector<int> v1 = {8, 1, 5, 2, 6}; 
    Solution ob; 
    cout << (ob.maxScoreSightseeingPair(v1)); 
    return 0; 
}

इनपुट

[8,1,5,2,6]

आउटपुट

11