ধরুন আমাদের কাছে nums এবং একটি পূর্ণসংখ্যা k নামক একটি অ্যারে আছে, আমাদের সেই অ্যারের একটি অ-খালি অনুসারির সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে পরবর্তীতে প্রতি দুটি পরপর সংখ্যার জন্য, nums[i] এবং nums[j], যেখানে i
আমরা জানি যে অ্যারে থেকে কিছু সংখ্যক উপাদান মুছে ফেলে, অবশিষ্ট উপাদানগুলিকে তাদের আসল ক্রমানুসারে রেখে একটি বিন্যাসের একটি অনুগামী পাওয়া যায়৷
সুতরাং, যদি ইনপুটটি [10,2,-9,5,19] এবং k =2 এর মত হয়, তাহলে আউটপুট হবে 36 কারণ পরবর্তী [10,2,5,19]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=-inf
-
একটি অ্যারে ডিপি সংজ্ঞায়িত করুন এবং এতে প্রদত্ত অ্যারেটি অনুলিপি করুন
-
একটি deque dq
সংজ্ঞায়িত করুন -
dq
এর শুরুতে v[0] ঢোকান -
n :=v
এর আকার -
ret :=v[0]
-
আরম্ভ করার জন্য i :=1, যখন i
-
যদি i> k এবং dq এর প্রথম উপাদান dp[i - k - 1] এর মত হয়, তাহলে
-
dq
থেকে সামনের উপাদান মুছুন
-
-
dp[i] :=সর্বাধিক dp[i] এবং (যদি dq খালি থাকে, তাহলে dp[i] + 0, অন্যথায় dp + dq[i]-এর প্রথম উপাদান)
-
যখন (dq খালি নয় এবং dq
-
dq
থেকে শেষ উপাদান মুছুন
-
-
dq
এর শেষে dp[i] ঢোকান -
ret :=সর্বোচ্চ ret এবং dp[i]
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h> using namespace std; const int inf = 1e9 + 10; class Solution { public: int constrainedSubsetSum(vector<int>& v, int k) { int ret = -inf; vector<int> dp(v.begin(), v.end()); deque<int> dq; dq.push_front(v[0]); int n = v.size(); ret = v[0]; for (int i = 1; i < n; i++) { if (i > k && dq.front() == dp[i - k - 1]) dq.pop_front(); dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] + dq.front()); while (!dq.empty() && dq.back() < dp[i]) dq.pop_back(); dq.push_back(dp[i]); ret = max(ret, dp[i]); } return ret; } }; main(){ Solution ob; vector<int> v = {10,2,-9,5,19}; cout << (ob.constrainedSubsetSum(v, 2)); }
ইনপুট
{10,2,-9,5,19}, 2
আউটপুট
36