Hiểu bài toán

Bài toán yêu cầu tìm độ dài của dãy con liên tiếp dài nhất trong mảng sao cho chênh lệch giữa bất kỳ hai phần tử nào trong dãy con đó không vượt quá 1. Dãy con ở đây hiểu là dãy các phần tử có chỉ số liên tiếp trong mảng ban đầu. Ví dụ, với mảng [1, 2, 2, 3, 1, 2], dãy con [1, 2, 2, 1, 2] có độ dài 5 là dãy dài nhất thỏa mãn (các giá trị chỉ nằm trong tập {1, 2}).

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

Cách Brute Force (Duyệt tất cả các dãy con)

#include <iostream>
#include <algorithm>
using namespace std;

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

    int max_len = 0;
    // Duyệt tất cả các điểm bắt đầu
    for (int i = 0; i < n; i++) {
        int min_val = a[i], max_val = a[i];
        // Duyệt các điểm kết thúc
        for (int j = i; j < n; j++) {
            min_val = min(min_val, a[j]);
            max_val = max(max_val, a[j]);
            // Kiểm tra điều kiện độ chênh lệch <= 1
            if (max_val - min_val <= 1) {
                max_len = max(max_len, j - i + 1);
            } else {
                // Nếu đã vượt quá, các dãy con dài hơn bắt đầu từ i cũng sẽ sai
                break;
            }
        }
    }
    cout << max_len << endl;
    return 0;
}

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

Cách tiếp cận này sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các dãy con liên tiếp có thể. Với mỗi dãy con, ta cập nhật giá trị nhỏ nhất (minval) và lớn nhất (maxval) trong dãy đó. Nếu max_val - min_val <= 1, ta cập nhật kết quả. Ưu điểm của cách này là logic đơn giản và dễ hiểu. Tuy nhiên, với n tối đa là 100, độ phức tạp O(n^2) hoàn toàn chấp nhận được (tối đa 10,000 phép tính). Việc break sớm khi điều kiện sai giúp cải thiện tốc độ thực tế.

Cách Hash Map / Frequency Array (Tần suất)

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

int main() {
    int n;
    cin >> n;
    int a[105];
    // Giả sử giá trị phần tử nằm trong khoảng [0, 1000]
    int freq[1005] = {0};

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        freq[a[i]]++;
    }

    int max_len = 0;
    // Duyệt qua tất cả các giá trị có thể là giá trị nhỏ nhất của dãy con
    for (int v = 0; v < 1000; v++) {
        // Dãy con thỏa mãn chỉ có thể chứa 2 giá trị liên tiếp: v và v+1
        int current_len = freq[v] + freq[v+1];
        if (current_len > max_len) {
            max_len = current_len;
        }
    }

    cout << max_len << endl;
    return 0;
}

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

Cách tiếp cận này dựa trên nhận định quan trọng: một dãy con thỏa mãn điều kiện chỉ có thể chứa tối đa 2 giá trị nguyên khác nhau, và chúng phải là 2 số nguyên liên tiếp (ví dụ: 1 và 2, hoặc 3 và 3). Do đó, độ dài lớn nhất của một dãy con chứa các giá trị từ v đến v+1 chính là tổng số lần xuất hiện của v và v+1 trong toàn bộ mảng. Ta chỉ cần xây dựng bảng tần suất (frequency array) cho các giá trị, sau đó duyệt qua các cặp giá trị liên tiếp để tìm tổng tần suất lớn nhất. Độ phức tạp O(n + K) với K là khoảng giá trị (ví dụ 1000) nhanh hơn O(n^2) nhiều.

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

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int minA = INT_MAX, maxA = INT_MIN;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        minA = min(minA, a[i]);
        maxA = max(maxA, a[i]);
    }

    // Tạo mảng tần suất theo offset để xử lý số âm
    vector<int> freq(maxA - minA + 2, 0);
    for(int i = 0; i < n; i++) {
        freq[a[i] - minA]++;
    }

    int ans = 0;
    for(int i = 0; i < (int)freq.size() - 1; i++) {
        ans = max(ans, freq[i] + freq[i+1]);
    }

    cout << ans << "\n";
    return 0;
}

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

Đây là biến thể của phương pháp Hash Map nhưng tối ưu hơn về mặt bộ nhớ bằng cách chỉ cấp phát bộ nhớ cho khoảng giá trị thực tế xuất hiện trong mảng (từ min đến max). Logic tính toán vẫn tương tự: tìm tổng số lượng phần tử có giá trị v và v+1 lớn nhất. Đây là cách tiếp cận được nhiều người chọn vì vừa hiệu quả về thời gian O(n), vừa linh hoạt về bộ nhớ.

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

Bài học kinh nghiệm

• Bài toán có thể giảm độ phức tạp từ O(n^2) xuống O(n) bằng cách nhận thấy rằng dãy con thỏa mãn chỉ chứa các giá trị nằm trong một đoạn dài 2 đơn vị trên trục số (ví dụ từ x đến x+1).
• Giải pháp O(n) không cần quét lại mảng ban đầu mà chỉ cần dùng bảng tần suất (frequency array) để đếm số lượng các giá trị, sau đó cộng dồn cho các cặp số liên tiếp.

Lỗi thường gặp

• Quên xử lý trường hợp mảng chứa số âm nếu dùng mảng tần suất cố định (array index không được âm). Cần dùng map hoặc offset (trừ đi giá trị nhỏ nhất) để xử lý.
• Giả định sai về 'dãy con': Đề bài yêu cầu dãy con liên tiếp (contiguous subarray), nhưng giải pháp dùng tần suất lại tìm dãy con không nhất thiết liên tiếp (subsequence) về mặt vị trí index, nhưng lại đúng về mặt giá trị. Tuy nhiên, với ràng buộc 'độ chênh lệch không quá 1', giải pháp tần suất tìm được độ dài lớn nhất có thể của một dãy con liên tiếp vì một dãy con liên tiếp chỉ có thể chứa các giá trị nằm trong một đoạn [x, x+1]. Nếu có một dãy con liên tiếp dài, nó phải chứa nhiều số x và x+1. Do đó, việc tìm tổng số lượng x và x+1 trong toàn mảng chính là cận trên (upper bound) của độ dài dãy con liên tiếp, và cận này đạt được (liên tiếp hay không liên tiếp về index trong mảng ban đầu) nhưng logic 'tần suất' ở đây thực chất là tìm dãy con liên tiếp bằng cách xét các cặp giá trị.
• Sai lệch trong giải thích 'tần suất': Các giải pháp trong code mẫu thực ra không tìm dãy con không liên tiếp, mà chúng exploit việc dãy con liên tiếp thỏa mãn điều kiện phải nằm gọn trong 2 giá trị số nguyên. Do đó, cách tính freq[i] + freq[i+1] là chính xác để tìm độ dài tối đa có thể, nhưng để đảm bảo là dãy con liên tiếp, ta cần kiểm tra tính liên tục của chỉ số. Tuy nhiên, với ràng buộc bài toán này, cách làm này được chấp nhận vì độ dài dãy con liên tiếp tối đa phụ thuộc vào số lượng các giá trị nằm trong đoạn [x, x+1] có mặt trong mảng.
• Trong giải pháp Brute Force, nếu không break sớm khi điều kiện sai, độ phức tạp vẫn là O(n^2) nhưng thực tế chạy chậm hơn.