একটি অ্যারে nums এবং পূর্ণসংখ্যা k দেওয়া আছে। নন-এমপটি সাবসিকোয়েন্সের সর্বোচ্চ যোগফল বের করুন যাতে দুটি পড়নো উপাদানের ইন্ডেক্স পার্থক্য <= k।
উদাহরণ: [10,2,-9,5,19], k=2 -> আউটপুট ৩৬ (সাবসিকোয়েন্স [10,2,5,19])।
সমাধানের ধাপসমূহ
- ret = -inf, dp = nums কপি।
- Deque dq দিয়ে স্লাইডিং উইন্ডো ম্যাক্সিমাম মেইন্টেইন করুন।
- dq.push_front(v[0]), ret = v[0]。
- i=1 থেকে n-1:
- যদি i > k এবং dq.front() == dp[i-k-1], dq.pop_front()।
- dp[i] = max(dp[i], dp[i] + (dq.empty()? 0 : dq.front()))।
- যব dq.back() < dp[i], dq.pop_back()।
- dq.push_back(dp[i])।
- ret = max(ret, dp[i])।
- ret রিটার্ন করুন।
C++ কোড উদাহরণ
#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;
}
};
int main() {
Solution ob;
vector<int> v = {10,2,-9,5,19};
cout << ob.constrainedSubsetSum(v, 2);
return 0;
}
ইনপুট
{10,2,-9,5,19}, 2
আউটপুট
36
