Giả sử chúng ta có một mảng với n phần tử. Vấn đề là tìm mảng con dài nhất có đúng k số lẻ. Vì vậy, nếu A =[2, 3, 4, 11, 4, 12, 7] và k =1, thì đầu ra sẽ là 4, mảng con là [4, 11, 4, 12]
Chúng tôi có thể giải quyết điều này bằng cách sử dụng cửa sổ trượt. Nhiệm vụ giống như bên dưới -
- Khởi tạo max:=0, count:=0 và start:=0
- đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện như sau
- nếu arr [i] mod 2 không phải là 0, thì hãy tăng số lượng lên 1
- while count> k và start <=i, thực hiện như sau
- nếu arr [start] mod 2 không phải là 0, thì hãy giảm số lượng đi 1
- tăng bắt đầu lên 1
- nếu count =k, thì
- nếu max <(i - start + 1), thì max:=(i - start + 1)
- trả về giá thầu tối đa
Ví dụ
#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);
} Đầu ra
Maximum Length is: 4