Hiểu bài toán

Cho một mảng gồm n số nguyên và một số nguyên dương L. Tìm tổng lớn nhất của một đoạn con liên tiếp có độ dài đúng L. Ví dụ, với mảng [1, 2, 3, 4, 5] và L = 2, đoạn con có tổng lớn nhất là [4, 5] với tổng là 9.

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

Cách Brute Force (Tính toán trực tiếp)

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

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

    long long maxSum = -1e18; // Khởi tạo giá trị âm rất lớn

    // 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 đoạn con độ dài L bắt đầu từ i
        for(int j = 0; j < L; j++) {
            currentSum += a[i + j];
        }
        maxSum = max(maxSum, currentSum);
    }

    cout << maxSum;
    return 0;
}

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

Cách tiếp cận này sử dụng hai 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 đoạn con (từ 0 đến n-L). Vòng lặp trong tính tổng các phần tử của đoạn con độ dài L bắt đầu từ vị trí đó. Мы so sánh và cập nhật tổng lớn nhất tìm được. Phương pháp này chậm vì mỗi đoạn con đều tính tổng lại từ đầu, dẫn đến nhiều phép tính lặp lại.

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

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

int main() {
    int n, l;
    cin >> n >> l;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int current_tong = 0;

    // Tính tổng của đoạn đầu tiên độ dài L
    for(int i = 0; i < l; i++){
        current_tong += a[i];
    }
    int max_tong = current_tong;

    // Trượt cửa sổ qua các phần tử còn lại
    for(int i = l; i < n; i++){
        // Trừ phần tử ra khỏi đầu cửa sổ và cộng phần tử mới vào cuối
        current_tong -= a[i - l];
        current_tong += a[i];
        if(current_tong > max_tong){
            max_tong = current_tong;
        }
    }
    cout << max_tong;

    return 0;
}

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

Đây là phương pháp tối ưu. Thay vì tính lại tổng từ đầu cho mỗi đoạn con, ta chỉ tính tổng của đoạn đầu tiên. Sau đó, khi di chuyển sang phải (trượt cửa sổ), ta trừ đi phần tử sắp rời khỏi cửa sổ và cộng thêm phần tử mới đi vào. Điều này giúp cập nhật tổng mới trong thời gian hằng số O(1). Vòng lặp chạy n lần, do đó độ phức tạp thời gian là O(n).

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, l;
    cin >> n >> l;
    vector<ll> a(n + 1);
    vector<ll> pre(n + 1, 0);

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

    ll ma = -1e18;
    for(ll i = 1; i <= n - l + 1; i++) {
        // Tổng đoạn từ i đến i+l-1 là pre[i+l-1] - pre[i-1]
        ll k = pre[i + l - 1] - pre[i - 1];
        ma = max(ma, k);
    }
    cout << ma;
    return 0;
}

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

Phương pháp này xây dựng một mảng cộng dồn (prefix sum) trong đó pre[i] là tổng các phần tử từ đầu mảng đến phần tử thứ i. Sau đó, tổng của bất kỳ đoạn con nào từ chỉ số L đến R có thể được tính bằng pre[R] - pre[L-1]. Điều này cho phép tính tổng của đoạn con độ dài L chỉ bằng một phép trừ, thay vì lặp lại L lần cộng. Độ phức tạp xây dựng mảng là O(n), và truy vấn O(1) cho mỗi đoạn, tổng cộng O(n).

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

Bài học kinh nghiệm

• Tránh tính toán lại các giá trị đã biết: Nếu các đoạn con giao nhau, ta có thể tận dụng kết quả tính toán của đoạn trước.
• Cửa sổ trượt (Sliding Window) là kỹ thuật phổ biến cho các bài toán dãy con liên tiếp có độ dài cố định.
• Tổng tiền tố (Prefix Sum) là một cấu trúc dữ liệu cơ bản giúp tính tổng con của mảng trong thời gian O(1) sau tiền xử lý O(n).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ (như int) dẫn đến tràn số khi tổng các phần tử vượt quá giới hạn của kiểu dữ liệu đó.
• Lỗi index out of bounds khi truy cập mảng, đặc biệt khi sử dụng mảng 1-indexed (vòng lặp nên chạy từ 1 đến n-L+1) hoặc 0-indexed (0 đến n-L).
• Quên khởi tạo giá trị max ban đầu nhỏ hơn tất cả các tổng có thể (ví dụ: -1e18) thay vì 0, trong khi các phần tử đầu vào có thể âm.