Hiểu bài toán

Cho một dãy gồm n số nguyên được sắp xếp trên một vòng tròn. Nhiệm vụ là tìm dãy con liên tiếp (trên vòng tròn) có tổng các phần tử nhỏ nhất. Dãy con phải có ít nhất một phần tử. Do dữ liệu nằm trên vòng tròn, một dãy con có thể bao gồm các phần tử từ cuối dãy nối tiếp phần tử đầu dãy.

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

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

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(2 * n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    long long kq = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = 1; j <= n; j++) {
            sum += a[i + j - 1];
            kq = min(kq, sum);
        }
    }
    cout << kq;
    return 0;
}

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

Cách tiếp cận này xử lý bài toán dãy con trên vòng tròn bằng cách 'bẻ cong' dãy thành một dãy có độ dài 2n. Sau đó, ta duyệt qua tất cả các dãy con có độ dài từ 1 đến n bắt đầu từ mọi vị trí i (0 <= i < n). Với mỗi độ dài, ta tính tổng các phần tử. Do n <= 100, độ phức tạp O(n^2) là hoàn toàn chấp nhận được.

Cách Optimized Logic (Tối ưu hóa logic)

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

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

    long long minEnd = a[0], minSum = a[0];
    long long maxEnd = a[0], maxSum = a[0];
    for (int i = 1; i < n; i++) {
        minEnd = min(a[i], minEnd + a[i]);
        minSum = min(minSum, minEnd);
        maxEnd = max(a[i], maxEnd + a[i]);
        maxSum = max(maxSum, maxEnd);
    }

    if (maxSum < 0) {
        cout << minSum;
        return 0;
    }
    if (maxSum == tongAll) {
        cout << minSum;
    } else {
        cout << min(minSum, tongAll - maxSum);
    }
    return 0;
}

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

Đây là cách tiếp cận tối ưu. Dãy con có tổng nhỏ nhất trên vòng tròn có thể là:

1. Một dãy con nằm hoàn toàn bên trong (không bao bọc đầu cuối) -> Dùng thuật toán Kadane để tìm dãy con có tổng nhỏ nhất (minSum).
2. Một dãy con bao bọc đầu cuối (vòng qua phần tử cuối nối đầu) -> Nếu dãy con này là dãy con có tổng nhỏ nhất, thì dãy còn lại (từ sau điểm kết thúc đến trước điểm bắt đầu) phải là dãy con có tổng lớn nhất (maxSum). Tổng của dãy con vòng tròn này bằng tổng toàn bộ dãy trừ đi maxSum.

Logic:

• Tính tổng toàn dãy (tongAll).
• Dùng Kadane tìm minSum (dãy con có tổng nhỏ nhất) và maxSum (dãy con có tổng lớn nhất).
• Nếu maxSum < 0: Toàn bộ dãy là số âm, dãy con có tổng nhỏ nhất chính là dãy có tổng nhỏ nhất (minSum).
• Nếu maxSum == tongAll: Dãy con có tổng lớn nhất là cả dãy, khi đó dãy con vòng tròn bao bọc đầu cuối sẽ rỗng hoặc không tồn tại dãy con âm bao bọc (vì tongAll dương hoặc 0), ta chỉ quan tâm đến minSum.
• Trường hợp còn lại: Dãy con vòng tròn bao bọc đầu cuối có tổng bằng tongAll - maxSum. Ta so snahs nó với minSum để tìm kết quả cuối cùng.

Cách Dynamic Programming (Kadane's Algorithm)

// Hỗn hợp giữa Logic và DP
#include <bits/stdc++.h>
using namespace std;

long long min_subarray_sum(long long a[], int n) {
    long long min_ending_here = a[0];
    long long min_so_far = a[0];
    for (int i = 1; i < n; i++) {
        min_ending_here = min(a[i], min_ending_here + a[i]);
        min_so_far = min(min_so_far, min_ending_here);
    }
    return min_so_far;
}

long long max_subarray_sum(long long a[], int n) {
    long long max_ending_here = a[0];
    long long max_so_far = a[0];
    for (int i = 1; i < n; i++) {
        max_ending_here = max(a[i], max_ending_here + a[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

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

    long long minSum = min_subarray_sum(a, n);
    long long maxSum = max_subarray_sum(a, n);

    if (maxSum < 0) {
        cout << minSum;
    } else if (maxSum == tongAll) {
        cout << minSum;
    } else {
        cout << min(minSum, tongAll - maxSum);
    }
    return 0;
}

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

Đây là cách diễn đạt thuật toán Kadane (Quy hoạch động) rõ ràng hơn cho bài toán này. Ta chia bài toán thành 2 trường hợp: dãy con không bao bọc đầu cuối và dãy con bao bọc đầu cuối. Dãy con bao bọc đầu cuối tương đương với việc tìm dãy con có tổng lớn nhất (maxSubarray) và lấy tổng toàn bộ trừ đi nó. Hàm minsubarraysum và maxsubarraysum thực hiện vai trò của Kadane. Đây là cách tiếp cận chuẩn để giải quyết bài toán dãy con trên vòng trôn một cách hiệu quả.

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

Bài học kinh nghiệm

• Bài toán dãy con trên vòng tròn có thể được giải quyết bằng cách chia thành 2 trường hợp: dãy con nằm gọn trong dãy thẳng và dãy con bao bọc đầu cuối.
• Dãy con bao bọc đầu cuối có tổng nhỏ nhất tương đương với tổng toàn dãy trừ đi dãy con có tổng lớn nhất.
• Thuật toán Kadane (Quy hoạch động) giúp giải quyết bài toán dãy con liên tiếp có tổng lớn/nhỏ nhất trong thời gian O(n).

Lỗi thường gặp

• Quên xử lý trường hợp tất cả các số đều âm, dẫn đến việc dãy con có tổng lớn nhất (maxSum) có thể nhỏ hơn 0, cần phải kiểm tra điều kiện này trước.
• Sai lệch trong việc tính toán chỉ số khi bẻ cong dãy (Approach 1) nếu không chú ý đến độ dài dãy con cho phép (tối đa n).
• Biến overflow khi tính tổng do |a_i| lên tới 10^9 và n <= 100, cần sử dụng kiểu dữ liệu 64-bit (long long).