একটি পূর্ণসংখ্যা অ্যারে দেওয়া থাকলে, তার সবচেয়ে দীর্ঘ হারমোনিয়াস সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে হবে। একটি হারমোনিয়াস সিকোয়েন্স হলো এমন একটি অ্যারে যেখানে সর্বোচ্চ এবং সর্বনিম্ন মানের পার্থক্য ঠিক ১।
উদাহরণ: ইনপুট [1,3,2,2,5,2,3,7] হলে আউটপুট হবে ৫, কারণ সবচেয়ে দীর্ঘ হারমোনিয়াস সাবসিকোয়েন্স হলো [3,2,2,2,3] (এখানে ৩ এবং ২-এর পার্থক্য ১)।
সমাধানের ধাপসমূহ
- একটি ম্যাপ (hash map) m সংজ্ঞায়িত করুন।
- অ্যারے nums-এর প্রতিটি উপাদান n এর জন্য m[n]-এর মান ১ বাড়ান।
- ম্যাপের প্রতিটি কী-মান জোড়া (k, v) এর জন্য:
- k+1 কীটি ম্যাপে আছে কিনা খুঁজুন (it := m.find(k+1))।
- যদি পাওয়া যায়, তবে max_ = max(max_, v + it->second) আপডেট করুন।
- max_ রিটার্ন করুন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findLHS(vector<int>& nums) {
unordered_map<int, int> m;
for (const int n : nums)
++m[n];
int max_ = 0;
for (const auto& [k, v] : m) {
auto it = m.find(k + 1);
if (it != m.end())
max_ = max(max_, v + it->second);
}
return max_;
}
};
int main() {
Solution ob;
vector<int> v = {2,4,3,3,6,3,4,8};
cout << ob.findLHS(v);
return 0;
}
ইনপুট
{2,4,3,3,6,3,4,8}
আউটপুট
5
