C++에서 정확히 k개의 홀수를 갖는 가장 긴 하위 배열 찾기

n개의 요소가 있는 하나의 배열이 있다고 가정합니다. 문제는 정확히 k개의 홀수를 갖는 가장 긴 하위 배열을 찾는 것입니다. 따라서 A =[2, 3, 4, 11, 4, 12, 7]이고 k =1이면 출력은 4가 되고 하위 배열은 [4, 11, 4, 12]

슬라이딩 윈도우를 사용하여 해결할 수 있습니다. 작업은 아래와 같습니다 -

• 최대:=0, 개수:=0, 시작:=0
• 0 ~ n – 1 범위의 i에 대해 다음을 수행합니다.
  • arr[i] mod 2가 0이 아니면 카운트를 1 증가시킵니다.
  • count> 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