Độ dài mảng con lớn nhất có tổng chẵn trong C++

Cho mảng Arr[] số nguyên. Tìm mảng con liên tiếp (subarray) dài nhất có tổng các phần tử là số chẵn.

Ví dụ

Arr = {2, 3, 5, 2, 6, 7} → Output: 4
Mảng con {5, 2, 6, 7} tổng = 20 (chẵn).

Arr = {5, 7, 7, 3, 4} → Output: 4
Mảng con {5, 7, 7, 3} tổng = 22 (chẵn).

Quan sát quan trọng

• Nếu tổng cả mảng chẵn → đáp án = N.
• Nếu tổng lẻ → phải loại bỏ ít nhất 1 phần tử lẻ. Để giữ độ dài lớn nhất, loại bỏ phần tử lẻ ở đầu hoặc cuối (gần biên nhất).
• Đáp án = max(N - firstOddIdx - 1, lastOddIdx).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

int maxEvenSumSubarray(int arr[], int n) {
    int totalSum = 0;
    for (int i = 0; i < n; i++) totalSum += arr[i];
    
    if (totalSum % 2 == 0) return n; // Toàn mảng đã chẵn
    
    int firstOdd = -1, lastOdd = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 != 0) {
            if (firstOdd == -1) firstOdd = i;
            lastOdd = i;
        }
    }
    // Loại bỏ phần tử lẻ ở đầu hoặc cuối
    return max(n - firstOdd - 1, lastOdd);
}

int main() {
    int arr[] = {1, 2, 6, 2, 4, 2};
    int n = 6;
    cout << "Do dai lon nhat: " << maxEvenSumSubarray(arr, n); // Output: 5
    return 0;
}

Kết quả

Do dai lon nhat: 5

Độ phức tạp

O(N) thời gian, O(1) bộ nhớ. Rất hiệu quả.