Cho mảng n phần tử, tìm mảng con dài nhất chứa đúng k số lẻ. Ví dụ A=[2,3,4,11,4,12,7], k=1 → độ dài 4 (mảng con [4,11,4,12]).
Dùng cửa sổ trượt: duy trì count số lẻ, mở rộng cửa sổ, nếu count > k thu hẹp từ trái.
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); }
Kết quả
Maximum Length is: 4