मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी है। समस्या सबसे लंबी उप-सरणी को खोजने की है जिसमें बिल्कुल k विषम संख्याएँ हैं। तो अगर ए =[2, 3, 4, 11, 4, 12, 7], और के =1, तो आउटपुट 4 होगा, उप-सरणी है [4, 11, 4, 12]
हम इसे स्लाइडिंग विंडो का उपयोग करके हल कर सकते हैं। कार्य नीचे जैसा है -
- अधिकतम प्रारंभ करें:=0, गणना करें:=0, और प्रारंभ करें:=0
- 0 से n-1 की सीमा में i के लिए, निम्न कार्य करें
- अगर arr[i] mod 2 0 नहीं है, तो 1 से गिनती बढ़ाएं
- गिनते समय> k और प्रारंभ करें <=i, निम्न कार्य करें
- अगर arr[start] mod 2 0 नहीं है, तो गिनती में 1 की कमी करें
- शुरुआत को 1 से बढ़ाएं
- अगर गिनती =के, तो
- यदि अधिकतम <(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