মান লেযিয়ে একটি ধনাত্মক পূর্ণসংখ্যা অ্যারে A দেওয়া আছে, এখানে A[i] উপস্থাপন করে i-তম সাইটসিইং স্পটের মান, এবং দুটি সাইটসিইং স্পট i এবং j-এর দূরত্ব j - i। এখন একটি পেয়ার (i < j)-এর স্কোর হবে এই ফর্মুলা অনুযায়ী (A[i] + A[j] + i - j): আমাদের সাইটসিইং স্পটের একটি পেয়ারের সর্বাধিক স্কোর খুঁজে বের করতে হবে। ইনপুট [8,1,5,2,6] হলে আউটপুট হবে ১১, কারণ i = 0, j = 2 হলে A[0] + A[2] + 0 - 2 = 8 + 5 + 0 - 2 = ১১।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
ret := 0, maxVal := 0, n := A.size() সেট করুন
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
ret := max(ret, maxVal + A[i] - i)
maxVal := max(A[i] + i, maxVal)
return ret
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
