ধরুন আমাদের কাছে nums এবং একটি পূর্ণসংখ্যা k নামক একটি অ্যারে আছে, আমাদের সেই অ্যারের একটি অ-খালি অনুসারির সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে পরবর্তীতে প্রতি দুটি পরপর সংখ্যার জন্য, nums[i] এবং nums[j], যেখানে i
আমরা জানি যে অ্যারে থেকে কিছু সংখ্যক উপাদান মুছে ফেলে, অবশিষ্ট উপাদানগুলিকে তাদের আসল ক্রমানুসারে রেখে একটি বিন্যাসের একটি অনুগামী পাওয়া যায়৷
সুতরাং, যদি ইনপুটটি [10,2,-9,5,19] এবং k =2 এর মত হয়, তাহলে আউটপুট হবে 36 কারণ পরবর্তী [10,2,5,19]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
ret :=-inf
একটি অ্যারে ডিপি সংজ্ঞায়িত করুন এবং এতে প্রদত্ত অ্যারেটি অনুলিপি করুন
একটি deque dq
dq
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
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
