Hiểu bài toán

Cho một dãy số nguyên gồm $N$ phần tử. Nhiệm vụ của bạn là tìm cặp số hạng cạnh nhau (i và i+1) có tổng lớn nhất sao cho một số hạng chẵn, số còn lại lẻ (tức là một chẵn một lẻ). Nếu không tồn tại cặp nào thỏa mãn, in ra -1.

Các cách tiếp cận

Cách Duyệt toàn bộ mảng (Iterative Approach)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("ChanLe.Inp", "r", stdin);
    freopen("ChanLe.Out", "w", stdout);
    long long n, maxSum = -1;
    cin >> n;
    vector<long long> a(n);
    for (auto &i : a) cin >> i;
    for (long long i = 1; i < n; i++) {
        // Kiểm tra điều kiện chẵn lẻ xen kẽ
        if ((a[i-1] % 2 == 0 && a[i] % 2 == 1) || (a[i-1] % 2 == 1 && a[i] % 2 == 0)) {
            maxSum = max(maxSum, a[i-1] + a[i]);
        }
    }
    cout << maxSum;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực tiếp nhất. Đọc toàn bộ dãy số vào mảng. Duyệt từ phần tử thứ 2 đến hết, kiểm tra xem phần tử hiện tại và phần tử trước đó có khác dấu chẵn lẻ không. Nếu có, tính tổng và cập nhật giá trị lớn nhất. Cần lưu ý sử dụng kiểu dữ liệu long long để tránh tràn số khi tính tổng.

Cách Tối ưu bộ nhớ (One-pass)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("ChanLe.Inp", "r", stdin);
    freopen("ChanLe.Out", "w", stdout);
    long long n, tong = -1;
    cin >> n;
    vector<long long> a(n);
    cin >> a[0];
    for (long long i = 1; i < n; i++) {
        cin >> a[i];
        if ((a[i-1] % 2 == 0 && a[i] % 2 == 1) || (a[i-1] % 2 == 1 && a[i] % 2 == 0)) {
            tong = max(tong, a[i] + a[i-1]);
        }
    }
    cout << tong;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Nâng cấp từ Approach 1. Thay vì lưu toàn bộ mảng, ta chỉ cần lưu phần tử trước đó (hoặc dùng mảng 2 phần tử). Điều này giảm bộ nhớ cần thiết đáng kể, đặc biệt hiệu quả với các dãy dài. Logic vẫn giữ nguyên: vừa đọc phần tử mới vừa so sánh với phần tử cũ để cập nhật kết quả.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chỉ quan tâm đến tính chẵn lẻ của các số hạng cạnh nhau, không quan trọng giá trị của chúng (ngoại trừ việc tính tổng).
• Sử dụng operator bitwise & 1 ((a+b)&1) là một cách kiểm tra chẵn lẻ nhanh hơn phép chia lấy dư % 2.
• Vì giới hạn của số nguyên có thể lớn, luôn ưu tiên sử dụng long long cho các biến tổng và giá trị.

Lỗi thường gặp

• Lỗi tràn số (Overflow): Nếu dùng int để lưu tổng của hai số lớn.
• Quên xử lý trường hợp không t tồn tại cặp thỏa mãn: Kết quả mặc định phải là -1.
• Truy cập ngoài mảng khi duyệt: Cần kiểm tra điều kiện i > 0 hoặc bắt đầu vòng lặp từ i = 1.