Editorial for ksum: Món quà của thầy Kiên

Hiểu bài toán

Bài toán yêu cầu tìm tổng độ ngon lớn nhất của một đoạn gồm k viên kẹo liên tiếp trong dãy n viên kẹo. Ta được cho mảng w gồm n phần tử, mỗi phần tử là độ ngon của một viên kẹo. Cần tìm chỉ số bắt đầu i sao cho tổng w[i] + w[i+1] + ... + w[i+k-1] là lớn nhất và in ra tổng đó.

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

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

#include<stdio.h>
#define ll long long

int main(){
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll a[100000];
    for (ll i = 0; i < n; i++){
        scanf("%lld",&a[i]);
    }
    ll sum = 0;

    for (ll i = 0; i < k; i++){
        sum += a[i];
    }
    ll max = sum;
    for (ll i = 0; i < n - k; i++){
        sum -= a[i];
        sum += a[k + i];
        if (sum > max) max = sum;
    }
    printf("%lld",max);
    return 0;
}

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

Phương pháp này tính tổng của k phần tử đầu tiên. Sau đó, di chuyển cửa sổ (window) một đơn vị sang phải: loại bỏ phần tử ở đầu cửa sổ và thêm phần tử mới ở cuối. Tổng mới được tính bằng cách lấy tổng cũ, trừ đi phần tử bị loại và cộng thêm phần tử mới. Ta cập nhật tổng lớn nhất trong suốt quá trình di chuyển. Độ phức tạp thời gian là O(n) vì duyệt qua mảng một lần, không gian O(n) để lưu mảng.

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

#include <stdio.h>

#define ll long long
#define max(a, b) ((a > b) ? a : b)

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    ll arr[n];
    for (int i = 0; i < n; i++)
        scanf("%lld", &arr[i]);
    ll prefixsum[n+1], ans = 0;
    prefixsum[0] = 0;
    for (int i = 0; i < n; i++)
        prefixsum[i+1] = prefixsum[i] + arr[i];
    for (int i = 0; i <= n-k; i++)
        ans = max(ans, prefixsum[i+k] - prefixsum[i]);
    printf("%lld", ans);
}

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

Ta xây dựng một mảng tổng tiền tố (prefix sum) prefixsum trong đó prefixsum[i] là tổng của i phần tử đầu tiên. Tổng của một đoạn từ chỉ số i đến j có thể tính nhanh bằng prefixsum[j+1] - prefixsum[i]. Với mỗi đoạn liên tiếp độ dài k, ta tính tổng và tìm giá trị lớn nhất. Độ phức tạp thời gian O(n) (một lần xây dựng prefix sum và một lần duyệt các đoạn), không gian O(n) để lưu prefix sum.

Cách Brute Force (Quy hoạch động)

#include <stdio.h>
#define ll long long

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int a[n];
    long long s = 0, maxx = 0;

    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < k; ++i) {
        s += a[i];
    }
    maxx = s;

    for (int i = 0; i < n - k; ++i) {
        s = s + a[k + i] - a[i];
        if (s > maxx) {
            maxx = s;
        }
    }

    printf("%lld\n", maxx);
    return 0;
}

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

Đây là cách tiếp cận Sliding Window nhưng được trình bày với biến lặp rõ ràng hơn. Tính tổng k phần tử đầu tiên, sau đó vòng lặp từ 0 đến n-k, mỗi bước cập nhật tổng bằng cách trừ phần tử ra khỏi cửa sổ và thêm phần tử mới vào. Đây là giải pháp tối ưu và phổ biến nhất cho bài toán này.

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

Bài học kinh nghiệm

• Bài toán có thể giải quyết hiệu quả bằng cách sử dụng kỹ thuật Sliding Window (Cửa sổ trượt) để tính tổng các đoạn liên tiếp độ dài k mà không cần tính lại toàn bộ tổng mỗi lần.
• Kỹ thuật Prefix Sum cũng là một cách hiệu quả để tính tổng của bất kỳ đoạn nào trong mảng trong thời gian O(1) sau tiền xử lý O(n).

Lỗi thường gặp

• Độ dài k có thể bằng n, cần đảm bảo vòng lặp cập nhật tổng không truy cập ngoài biên mảng.
• Giá trị w_i lên tới 10^9 và n lên tới 10^5, tổng có thể lên tới 10^14, cần sử dụng kiểu dữ liệu 64-bit (long long trong C/C++) để tránh tràn số.
• Trong giải pháp Prefix Sum, cần phân biệt giữa chỉ số mảng 0-indexed và chỉ số prefix sum 1-indexed để tính toán chính xác.