मान लीजिए कि हमारे पास धनात्मक पूर्णांकों की एक सरणी A है, अब A[i] i-वें दर्शनीय स्थल के मान का प्रतिनिधित्व करता है, और दो दर्शनीय स्थल i और j की दूरी j-i है। अब दर्शनीय स्थलों की एक जोड़ी (i
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
सेट रिट:=0, मैक्सवैल:=0, सेट एन:=ए का आकार
मेरे लिए 0 से n - 1 की सीमा में
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
