ความยาวซับอาร์เรย์สูงสุดที่ผลรวมเป็นเลขคู่ใน C++

ภาพรวมปัญหา

หาซับอาร์เรย์ที่ยาวที่สุดซึ่งผลรวมของอิลิเมนต์เป็นเลขคู่

ตัวอย่าง

Input: Arr[] = {2, 3, 5, 2, 6, 7}
Output: 4
Subarray: {5, 2, 6, 7} sum = 20 (even)

Input: Arr[] = {5, 7, 7, 3, 4}
Output: 4
Subarray: {5, 7, 7, 3} sum = 22 (even)

แนวทางแก้ปัญหา

• ถ้าผลรวมทั้งอาร์เรย์เป็นคู่ -> ตอบคือ N
• ถ้าเป็นคี่ -> หาตัวเลขคี่ตัวแรกและตัวสุดท้าย ลบออกด้านไหนให้เหลือยาวกว่า

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int Length(int arr[], int n) {
    int sum = 0, leng = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    if (sum % 2 == 0) return n;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 1)
            leng = max(i, n - i - 1);
    }
    return leng;
}

int main() {
    int Arr[] = { 1, 2, 6, 2, 4, 2 };
    int size = 6;
    cout << "Maximum length: " << Length(Arr, size);
    return 0;
}

ผลลัพธ์

Maximum length of subarray such that sum of the subarray is even: 5