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