Hiểu bài toán

Cho một mảng gồm n số nguyên. Nhiệm vụ của bạn là tìm giá trị nhỏ nhất của tổng các phần tử trong một đoạn con liên tiếp bất kỳ của mảng. Đoạn con có thể rỗng (tổng bằng 0) hoặc chứa một phần tử hay nhiều phần tử. Tuy nhiên, dựa trên các giải pháp nộp vào, bài toán yêu cầu tìm tổng đoạn con liên tiếp có giá trị nhỏ nhất (minimum subarray sum), và đoạn con rỗng không được xét (vì kết quả trả về cho mảng toàn số dương sẽ là số dương nhỏ nhất). Cụ thể, ta cần tìm min_{1<=i<=j<=n} (sum(a[i..j])).

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

Cách Quy hoạch động (Dynamic Programming)

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

int main() {
    freopen("SUBSEQ.INP", "r", stdin);
    freopen("SUBSEQ.OUT", "w", stdout);

    int n;
    cin >> n;
    long long x;
    long long current_sum = 0;
    long long best = LLONG_MAX;

    for (int i = 0; i < n; i++) {
        cin >> x;
        if (i == 0) {
            current_sum = x;
        } else {
            current_sum = min(x, current_sum + x);
        }
        best = min(best, current_sum);
    }

    cout << best;
    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất, dựa trên thuật toán Kadane. Giả sử dp[i] là tổng đoạn con liên tiếp kết thúc tại chỉ số i có giá trị nhỏ nhất. Công thức truy hồi: dp[i] = min(a[i], dp[i-1] + a[i]). Ý nghĩa: để có đoạn con kết thúc tại i với tổng nhỏ nhất, ta hoặc chỉ lấy mỗi phần tử a[i], hoặc nối a[i] vào đoạn con có tổng nhỏ nhất kết thúc tại i-1. Ta chỉ cần duy nhất biến current_sum để lưu giá trị dp hiện tại và biến best để lưu giá trị nhỏ nhất tìm được. Vòng lặp duyệt qua mảng một lần.

Cách Brute Force (Naive)

// Pseudo-code for Brute Force
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

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

    long long min_sum = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        long long current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += a[j];
            min_sum = min(min_sum, current_sum);
        }
    }
    cout << min_sum;
    return 0;
}

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

Cách tiếp cận trực quan nhất là thử tất cả các đoạn con liên tiếp có thể. Dùng hai vòng lặp lồng nhau, vòng lặp ngoài chọn điểm bắt đầu i và vòng lặp trong chọn điểm kết thúc j. Tính tổng a[i] + ... + a[j] và cập nhật giá trị nhỏ nhất. Phương pháp này đúng nhưng quá chậm cho các bộ input lớn.

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

Bài học kinh nghiệm

• Bài toán này là biến thể của bài toán tìm tổng đoạn con lớn nhất (Maximum Subarray Sum), chỉ cần thay min thành max.
• Biến current_sum trong thuật toán Kadane đại diện cho đoạn con liên tiếp có tổng cực tiểu kết thúc tại vị trí hiện tại.
• Giá trị khởi tạo best = LLONG_MAX (hoặc a[0]) để đảm bảo tính đúng đắn cho trường hợp mảng chỉ có 1 phần tử.

Lỗi thường gặp

• Quên xử lý trường hợp n=1 hoặc khởi tạo sai giá trị ban đầu của biến best.
• Sử dụng biến kiểu int导致 overflow nếu các phần tử trong mảng hoặc tổng có giá trị lớn. Nên dùng long long.
• Lầm tưởng thuật toán Kadane thông thường (tìm max) có thể áp dụng trực tiếp nếu không đọc kỹ yêu cầu (tìm min).