สมมติว่าเรามีหนึ่งอาร์เรย์ที่มีองค์ประกอบ 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 – start + 1) แล้ว max :=(i – start + 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
