ধরুন আমাদের n উপাদান সহ একটি অ্যারে আছে। সমস্যা হল দীর্ঘতম সাব-অ্যারে খুঁজে বের করা যার ঠিক k বিজোড় সংখ্যা রয়েছে। তাই যদি A =[2, 3, 4, 11, 4, 12, 7] এবং k =1 হয়, তাহলে আউটপুট হবে 4, সাব-অ্যারে হল [4, 11, 4, 12]
আমরা স্লাইডিং উইন্ডো ব্যবহার করে এটি সমাধান করতে পারি। কাজটি নিচের মত -
- সর্বোচ্চ শুরু করুন :=0, গণনা :=0, এবং শুরু করুন :=0
- 0 থেকে n – 1 রেঞ্জের জন্য, নিম্নলিখিতগুলি করুন
- যদি arr[i] mod 2 0 না হয়, তাহলে গণনা 1 দ্বারা বাড়ান
- গণনা করার সময়> k এবং শুরু করুন <=i, নিম্নলিখিতগুলি করুন
- যদি arr[start] mod 2 0 না হয়, তাহলে গণনা 1 কমিয়ে দিন
- শুরু 1 দ্বারা বৃদ্ধি করুন
- যদি গণনা =k, তাহলে
- যদি সর্বোচ্চ <(i – শুরু + 1), তারপর সর্বোচ্চ :=(i – শুরু + 1)
- সর্বোচ্চ ফেরত দিন
উদাহরণ
#include<iostream>
using namespace std;
int oddSubarrayMaxLength(int arr[], int n, int k) {
int max_len = 0, count = 0, start = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 != 0)
count++;
while (count > k && start <= i)
if (arr[start++] % 2 != 0)
count--;
if (count == k)
if (max_len < (i - start + 1))
max_len = i - start + 1;
}
return max_len;
}
int main() {
int arr[] = {2, 3, 4, 11, 4, 12, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 1;
cout << "Maximum Length is: "<< oddSubarrayMaxLength(arr, n, k);
} আউটপুট
Maximum Length is: 4
