Editorial for maxsum: Dãy con có tổng lớn nhất

Hiểu bài toán

Bài toán yêu cầu tìm dãy con liên tiếp của mảng A có tổng lớn nhất và in ra tổng đó. Dãy con liên tiếp có nghĩa là các phần tử phải đứng cạnh nhau trong mảng. Ví dụ, với mảng [1, -3, 3], dãy con có tổng lớn nhất là [3] (hoặc [1, -3, 3] có tổng 1) nhưng thực tế [3] hoặc [1, -3, 3] có tổng 1, nhưng [3] có tổng 3 là lớn nhất. Đáp án là 3. Bài toán này còn được gọi là Maximum Subarray Problem.

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

Cách Quy hoạch động (Kadane's Algorithm)

#include <stdio.h>

int main() {
    long long n, x, sht, smax;
    scanf("%lld", &n);

    scanf("%lld", &x);
    sht = smax = x;

    while (--n) {
        scanf("%lld", &x);
        sht = (sht + x > x) ? sht + x : x;
        smax = (smax > sht) ? smax : sht;
    }

    printf("%lld", smax);
    return 0;
}

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

Đây là thuật toán Kadane, cách tiếp cận hiệu quả nhất. Ta duyệt qua mảng từ đầu đến cuối, duy trì biến sht (sum hiện tại) là tổng lớn nhất của dãy con liên tiếp kết thúc tại vị trí hiện tại. Công thức cập nhật: sht = max(sht + A[i], A[i]). Nếu tổng dãy con trước đó là âm, việc cộng thêm A[i] sẽ giảm tổng, nên ta bắt đầu một dãy con mới tại A[i]. Bien smax lưu tổng lớn nhất tìm được. Độ phức tạp thời gian O(n) và không gian O(1).

Cách Brute Force (Vét cạn)

#include <stdio.h>
#include <limits.h>

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

    long long max_sum = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        long long current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += a[j];
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }
    }
    printf("%lld", max_sum);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Sử dụng hai vòng lặp lồng nhau để thử tất cả các dãy con liên tiếp có thể. Vòng lặp ngoài chọn điểm bắt đầu, vòng lặp trong chọn điểm kết thúc. Với mỗi dãy con, tính tổng và so sánh với tổng lớn nhất hiện tại. Phương pháp này đúng nhưng chậm, chỉ khả thi với N nhỏ (N <= 1000 theo đề bài, nhưng N <= 100000 sẽ bị TLE).

Cách Optimized Brute Force (Prefix Sum)

#include <stdio.h>
#include <limits.h>

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

    long long max_sum = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            long long sum = pre[i] - pre[j];
            if (sum > max_sum) max_sum = sum;
        }
    }
    printf("%lld", max_sum);
    return 0;
}

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

Sử dụng mảng tổng tiền tố (prefix sum) để tính tổng dãy con trong O(1) sau khi đã preprocess. Tổng dãy con từ index i đến j là pre[j+1] - pre[i]. Tuy nhiên, vẫn cần vòng lặp lồng để duyệt qua tất cả các cặp (i, j). Độ phức tạp vẫn là O(n^2).

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

Bài học kinh nghiệm

• Bài toán Maximum Subarray có thể giải quyết hiệu quả bằng thuật toán Kadane.
• Biến 'sum hiện tại' (current sum) nên được reset về giá trị phần tử hiện tại nếu nó âm (tức là tổng dãy con trước đó âm).

Lỗi thường gặp

• Quên xử lý trường hợp mảng toàn số âm (ví dụ: [-3, -1, -2]). Thuật toán Kadane chuẩn phải hoạt động đúng (trả về -1).
• Sử dụng biến kiểu int cho tổng trong khi A_i có thể lên tới 10^9 và N=1000, tổng có thể tràn số (Overflow). Cần dùng long long.