สมมติว่ามีอาร์เรย์ที่มี n องค์ประกอบ ปัญหาคือการหาสับอาร์เรี่ยาวที่สุดที่มีเลขคี่พอดี k ตัว ดังนั้นถ้า A = [2, 3, 4, 11, 4, 12, 7] และ k = 1 ผลลัพธ์จะเป็น 4 สับอาร์เรย์คือ [4, 11, 4, 12]
เราสามารถแก้ได้โดยใช้ Sliding Window (หน้าต่างเลื่อน) งานคือดังนี้:
- เริ่มต้น max := 0, count := 0 และ start := 0
- สำหรับ i ในช่วง 0 ถึง n – 1 ทำดังนี้
- ถ้า arr[i] mod 2 ไม่ใช่ 0 ให้เพิ่ม count ขึ้น 1
- ขณะที่ count > k และ start <= i ทำดังนี้
- ถ้า arr[start] mod 2 ไม่ใช่ 0 ให้ลด count ลง 1
- เพิ่ม start ขึ้น 1
- ถ้า count = k แล้ว
- ถ้า max < (i – start + 1) ให้ max := (i – start + 1)
- คืนค่า max
ตัวอย่าง
#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
