Hiểu bài toán

Cho một mảng gồm n số nguyên và một số nguyên L. Nhiệm vụ của bạn là tìm tổng lớn nhất của một mảng con liên tiếp có độ dài chính xác L. Ví dụ: với mảng [1, 2, 3, 4, 5] và L = 2, các mảng con cần xét là [1,2], [2,3], [3,4], [4,5]. Tổng lớn nhất là 9 (từ [4,5]).

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

Cách Brute Force (Tính lại tổng từ đầu)

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

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

    long long maxSum = LLONG_MIN;
    // Duyệt qua tất cả các vị trí bắt đầu có thể
    for(int i = 0; i <= n - L; i++) {
        long long currentSum = 0;
        // Tính tổng L phần tử từ vị trí i
        for(int j = 0; j < L; j++) {
            currentSum += a[i + j];
        }
        maxSum = max(maxSum, currentSum);
    }
    cout << maxSum;
}

• Time Complexity: O(n * L)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng 2 vòng lặp lồng nhau. Vòng lặp ngoài duyệt qua tất cả các vị trí bắt đầu của mảng con (từ 0 đến n-L). Vòng lặp trong tính tổng các phần tử của mảng con bắt đầu tại vị trí đó. Đây là cách giải quyết trực quan nhất nhưng không hiệu quả về mặt thời gian thi hành.

Cách Sliding Window (Cửa sổ trượt)

#include <iostream>
#include <vector>
using namespace std;

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

    // Tính tổng cho cửa sổ đầu tiên
    long long sum = 0;
    for(int i = 0; i < L; i++) sum += a[i];

    long long maxSum = sum;
    // Trượt cửa sổ sang phải 1 đơn vị mỗi bước
    for(int i = L; i < n; i++) {
        // trừ đi phần tử ra khỏi cửa sổ, cộng thêm phần tử mới vào
        sum = sum - a[i - L] + a[i];
        if (sum > maxSum) maxSum = sum;
    }
    cout << maxSum;
}

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

Phương pháp này tối ưu hóa bằng cách không tính lại toàn bộ tổng từ đầu. Nó tính tổng của L phần tử đầu tiên, sau đó ở mỗi bước di chuyển cửa sổ sang phải 1 vị trí, nó chỉ cần trừ đi phần tử cũ nhất (ra khỏi cửa sổ) và cộng thêm phần tử mới nhất (vào cửa sổ). Điều này giảm đáng kể số lượng phép tính.

Cách Prefix Sum (Tổng tiền tố)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, L;
    cin >> n >> L;
    vector<long long> a(n);
    vector<long long> pre(n + 1, 0);

    for(int i = 1; i <= n; i++) {
        cin >> a[i-1];
        pre[i] = pre[i - 1] + a[i-1];
    }

    long long ans = -1e18;
    // Duyệt qua các đoạn có độ dài L
    for(int i = L; i <= n; i++) {
        long long currentSum = pre[i] - pre[i - L];
        ans = max(ans, currentSum);
    }
    cout << ans;
}

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

Phương pháp này xây dựng mảng tổng tiền tố pre, trong đó pre[i] là tổng của a[0] đến a[i-1]. Tổng của một đoạn từ a[i] đến a[j] có thể tính nhanh bằng pre[j+1] - pre[i]. Để tìm tổng đoạn dài L, ta chỉ cần tính pre[i] - pre[i-L]. Phương pháp này cũng chạy trong O(n) nhưng dùng thêm bộ nhớ cho mảng tổng tiền tố.

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

Bài học kinh nghiệm

• Bài toán này là một dạng cơ bản của thuật toán Sliding Window (Cửa sổ trượt).
• Việc tính lại toàn bộ tổng cho mỗi vị trí là nguyên nhân gây chậm, cần tận dụng kết quả của bước tính trước đó.

Lỗi thường gặp

• Sử dụng biến lưu tổng có kiểu dữ liệu quá nhỏ (ví dụ: int) dẫn đến tràn số khi tổng các phần tử vượt quá giới hạn của int (nên dùng long long).
• Lỗi chỉ số mảng (off-by-one error) khi chuyển đổi từ cách tiếp cận Brute Force sang Sliding Window hoặc Tổng tiền tố.