Hiểu bài toán

Cho một mảng gồm $N$ số nguyên $A$. Tìm tổng lớn nhất của 3 phần tử liên tiếp trong mảng và số lượng cách chọn 3 phần tử liên tiếp đó (các chỉ số $i, i+1, i+2$) để đạt được tổng lớn nhất đó.

• Dữ liệu: $N \le 10^6$, $|A_i| \le 10^9$.
• Đầu vào: Số nguyên $N$, sau đó là $N$ số nguyên của mảng $A$.
• Đầu ra: Hai số nguyên: tổng lớn nhất và số cách chọn tương ứng.
• Nếu $N < 3$, không thể tạo nhóm 3 người, đầu ra là 0 0 (theo các giải pháp đã cho).

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

Cách Duyệt trực tiếp (Truy vấn tiền tố)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    if (n < 3) {
        cout << "0 0";
        return 0;
    }

    vector<long long> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        arr[i] = arr[i - 1] + x;
    }

    long long max_sum = LLONG_MIN;
    long long count = 0;

    for (int i = 1; i + 2 <= n; i++) {
        long long current_sum = arr[i + 2] - arr[i - 1];
        if (current_sum > max_sum) {
            max_sum = current_sum;
            count = 1;
        } else if (current_sum == max_sum) {
            count++;
        }
    }

    cout << max_sum << ' ' << count;
    return 0;
}

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

Phương pháp này sử dụng truy vấn tiền tố (Prefix Sum) để tính tổng nhanh.

1. Đọc dữ liệu và xây dựng mảng cộng dồn arr, trong đó arr[i] là tổng các phần tử từ $A[1]$ đến $A[i]$.
2. Tổng của 3 phần tử liên tiếp tại vị trí $i$ (từ $A[i]$ đến $A[i+2]$) được tính bằng arr[i+2] - arr[i-1].
3. Duyệt qua tất cả các vị trí $i$ từ 1 đến $N-2$, cập nhật tổng lớn nhất và số lượng cách chọn.

Ưu điểm: Logic rõ ràng, dễ hiểu. Nhược điểm: Cần bộ nhớ $O(N)$ để lưu mảng cộng dồn, dù có thể tối ưu hơn.

Cách Duyệt trực tiếp (Không dùng truy vấn tiền tố)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    if (n < 3) {
        cout << "0 0";
        return 0;
    }

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long max_sum = a[0] + a[1] + a[2];
    long long count = 1;

    for (int i = 1; i < n - 2; ++i) {
        long long current_sum = a[i] + a[i+1] + a[i+2];
        if (current_sum > max_sum) {
            max_sum = current_sum;
            count = 1;
        } else if (current_sum == max_sum) {
            count++;
        }
    }

    cout << max_sum << " " << count;
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất.

1. Đọc toàn bộ mảng $A$ vào bộ nhớ.
2. Tính tổng của 3 phần tử đầu tiên làm giá trị khởi điểm cho max_sum.
3. Duyệt từ phần tử thứ 2 (index 1) đến $N-3$, tính tổng 3 phần tử liên tiếp tại mỗi bước.
4. Cập nhật max_sum và count nếu tìm thấy tổng lớn hơn hoặc bằng.

Phương pháp này không cần tính toán phức tạp, chỉ cần truy cập mảng trực tiếp.

Cách Tối ưu bộ nhớ (Không lưu mảng)

#include <iostream>
#include <climits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    if (n < 3) {
        cout << "0 0";
        return 0;
    }

    long long a, b, c, d;
    cin >> a >> b >> c;
    long long max_sum = a + b + c;
    long long count = 1;

    for (int i = 3; i < n; ++i) {
        cin >> d;
        // Tính tổng mới: a,b,c là 3 số trước đó, d là số mới
        // Nhóm hiện tại tại vị trí i-2, i-1, i là b, c, d
        long long current_sum = b + c + d;

        if (current_sum > max_sum) {
            max_sum = current_sum;
            count = 1;
        } else if (current_sum == max_sum) {
            count++;
        }

        // Dịch cửa sổ trượt: a, b, c -> b, c, d
        a = b;
        b = c;
        c = d;
    }

    cout << max_sum << " " << count;
    return 0;
}

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

Phương pháp này tối ưu nhất về bộ nhớ.

1. Thay vì lưu toàn bộ mảng, ta chỉ cần duy trì 3 biến lưu giá trị của 3 phần tử gần nhất (hoặc sử dụng một cửa sổ trượt).
2. Ban đầu, đọc 3 số đầu tiên để tính tổng đầu tiên.
3. Với mỗi số mới đọc được, tính tổng của cặp 3 số mới (bao gồm số vừa đọc), so sánh và cập nhật.
4. Sau đó cập nhật lại các biến lưu giá trị.

Phương pháp này phù hợp với các bài toán có giới hạn bộ nhớ nghiêm ngặt, mặc dù với $N=10^6$ thì bộ nhớ $O(N)$ của C++ thường vẫn chấp nhận được.

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

Bài học kinh nghiệm

• Sử dụng long long là bắt buộc vì tổng của 3 số có thể lên tới $3 \times 10^9$, vượt quá giới hạn của kiểu int (khoảng $2 \times 10^9$).
• Bài toán có thể giải quyết bằng thuật toán Sliding Window (Cửa sổ trượt) với kích thước cố định là 3.
• Cần xử lý trường hợp $N < 3$ ở đầu chương trình để tránh lỗi truy cập ngoài mảng.

Lỗi thường gặp

• Quên khởi tạo biến max_sum với một giá trị rất nhỏ (ví dụ: LLONG_MIN) hoặc khởi tạo sai giá trị ban đầu dẫn đến kết quả không chính xác nếu các tổng đều âm.
• Sử dụng int để lưu trữ tổng hoặc giá trị mảng, gây tràn số (overflow) khi $|A_i|$ lớn.
• Vòng lặp duyệt không đúng giới hạn (ví dụ: i <= n - 3 thay vì i < n - 2 trong trường hợp 0-indexed), dẫn đến bỏ sót các nhóm cuối hoặc lỗi truy cập.