Khóa học CTDL và GT

Bài 25.3. Ứng dụng trong bài toán tìm kiếm

Chào mừng trở lại với series về Cấu trúc Dữ liệu và Giải thuật!

Trong thế giới lập trình và cuộc sống hàng ngày, chúng ta liên tục đối mặt với nhu cầu tìm kiếm một thứ gì đó. Từ việc tìm kiếm một tập tin trên máy tính, một cuốn sách trong thư viện, một sản phẩm trên trang thương mại điện tử, hay đơn giản là tìm kiếm một số điện thoại trong danh bạ, tất cả đều là những ví dụ kinh điển của bài toán tìm kiếm.

Bài toán tìm kiếm cơ bản có thể phát biểu như sau: Cho một tập hợp các phần tử và một giá trị mục tiêu, hãy xác định xem giá trị mục tiêu có tồn tại trong tập hợp đó hay không, và nếu có thì nó nằm ở vị trí nào.

Tưởng chừng đơn giản, nhưng hiệu quả của việc tìm kiếm lại phụ thuộc rất nhiều vào cách chúng ta tổ chức dữ liệu (Cấu trúc dữ liệu) và chiến lược chúng ta sử dụng để tìm kiếm (Giải thuật). Hôm nay, chúng ta sẽ đi sâu vào hai trong số những thuật toán tìm kiếm cơ bản và phổ biến nhất, cùng với cách chúng được ứng dụng.

1. Tìm kiếm Tuần tự (Linear Search / Sequential Search)

Đây là thuật toán tìm kiếm đơn giản nhất và trực quan nhất.

Ý tưởng: Duyệt qua từng phần tử của tập hợp từ đầu đến cuối, so sánh từng phần tử với giá trị mục tiêu. Nếu tìm thấy phần tử nào khớp với mục tiêu, ta trả về vị trí của nó. Nếu duyệt hết tập hợp mà không tìm thấy, tức là mục tiêu không tồn tại.

Ưu điểm:

• Đơn giản: Dễ hiểu và dễ cài đặt.
• Không yêu cầu dữ liệu có trật tự: Hoạt động tốt trên cả các tập hợp dữ liệu chưa được sắp xếp.

Nhược điểm:

• Kém hiệu quả: Đặc biệt với các tập hợp dữ liệu lớn.

Độ phức tạp thời gian (Time Complexity):

• Trường hợp tốt nhất (Best Case): O(1) - Khi phần tử mục tiêu là phần tử đầu tiên của tập hợp.
• Trường hợp xấu nhất (Worst Case): O(n) - Khi phần tử mục tiêu là phần tử cuối cùng của tập hợp hoặc không tồn tại trong tập hợp (phải duyệt toàn bộ n phần tử).
• Trường hợp trung bình (Average Case): O(n) - Trung bình cũng phải duyệt qua một nửa tập hợp.

Nhìn chung, độ phức tạp của Tìm kiếm Tuần tự là O(n), nghĩa là thời gian thực hiện tỷ lệ thuận với kích thước của dữ liệu.

Ứng dụng thực tế của Tìm kiếm Tuần tự:

Mặc dù kém hiệu quả với dữ liệu lớn, Tìm kiếm Tuần tự vẫn có chỗ đứng trong các trường hợp sau:

• Tìm kiếm trên các tập hợp dữ liệu kích thước nhỏ.
• Tìm kiếm trên các tập hợp dữ liệu chưa được sắp xếp khi chi phí sắp xếp lại dữ liệu là quá lớn hoặc không cần thiết.
• Đôi khi được sử dụng bên trong các thuật toán phức tạp hơn.
• Ví dụ: Tìm một tên trong danh sách sinh viên chưa sắp xếp, tìm một giao dịch cụ thể trong lịch sử giao dịch không theo thứ tự thời gian.

Ví dụ minh họa bằng C++:

Giả sử chúng ta có một mảng các số nguyên chưa được sắp xếp và muốn tìm vị trí của một số cụ thể.

#include <iostream>
#include <vector> // Sử dụng vector thay vì mảng tĩnh cho tiện lợi

// Hàm thực hiện Tìm kiếm Tuần tự
// arr: vector chứa dữ liệu
// n: kích thước của vector
// target: giá trị cần tìm
// Trả về chỉ mục của target nếu tìm thấy, ngược lại trả về -1
int linearSearch(const std::vector<int>& arr, int n, int target) {
    // Duyệt qua từng phần tử từ đầu (chỉ mục 0) đến cuối (chỉ mục n-1)
    for (int i = 0; i < n; ++i) {
        // So sánh phần tử hiện tại với giá trị mục tiêu
        if (arr[i] == target) {
            // Nếu khớp, trả về chỉ mục của phần tử đó
            return i;
        }
    }
    // Nếu duyệt hết vòng lặp mà không tìm thấy, trả về -1
    return -1;
}

int main() {
    std::vector<int> myVector = {15, 8, 23, 42, 10, 5, 30, 50};
    int n = myVector.size(); // Kích thước của vector
    int target1 = 42; // Giá trị cần tìm có trong vector
    int target2 = 99; // Giá trị cần tìm không có trong vector

    // Tìm kiếm target1
    int result1 = linearSearch(myVector, n, target1);

    if (result1 != -1) {
        std::cout << "Tim thay " << target1 << " tai chi muc: " << result1 << std::endl;
    } else {
        std::cout << target1 << " khong ton tai trong vector." << std::endl;
    }

    // Tìm kiếm target2
    int result2 = linearSearch(myVector, n, target2);

    if (result2 != -1) {
        std::cout << "Tim thay " << target2 << " tai chi muc: " << result2 << std::endl;
    } else {
        std::cout << target2 << " khong ton tai trong vector." << std::endl;
    }

    return 0;
}

Giải thích code:

1. Chúng ta định nghĩa hàm linearSearch nhận vào một vector<int>, kích thước của nó (n), và giá trị target cần tìm.
2. Vòng lặp for (int i = 0; i < n; ++i) duyệt qua từng chỉ mục từ 0 đến n-1.
3. Bên trong vòng lặp, if (arr[i] == target) kiểm tra xem phần tử tại chỉ mục hiện tại (arr[i]) có bằng giá trị target hay không.
4. Nếu bằng, hàm trả về ngay lập tức chỉ mục i.
5. Nếu vòng lặp kết thúc mà điều kiện if không bao giờ đúng, nghĩa là không tìm thấy target, hàm sẽ trả về -1.
6. Trong hàm main, chúng ta tạo một vector mẫu, xác định các giá trị cần tìm (target1, target2), gọi hàm linearSearch và in kết quả tương ứng.

2. Tìm kiếm Nhị phân (Binary Search)

Trái ngược với Tìm kiếm Tuần tự, Tìm kiếm Nhị phân là một thuật toán hiệu quả hơn rất nhiều, nhưng nó có một yêu cầu cực kỳ quan trọng: Dữ liệu phải được SẮP XẾP.

Ý tưởng: Thay vì duyệt tuần tự, Tìm kiếm Nhị phân áp dụng chiến lược "chia để trị". Nó hoạt động như sau:

1. Xác định phần tử nằm ở giữa tập hợp dữ liệu hiện tại (phạm vi tìm kiếm).
2. So sánh phần tử giữa này với giá trị mục tiêu (target).
3. Có 3 trường hợp xảy ra:
   • Nếu phần tử giữa bằng target: Tìm thấy! Trả về vị trí của nó.
   • Nếu target nhỏ hơn phần tử giữa: Điều này có nghĩa là target (nếu tồn tại) chỉ có thể nằm ở nửa bên trái của phần tử giữa. Ta loại bỏ nửa bên phải và tiếp tục tìm kiếm trên nửa bên trái.
   • Nếu target lớn hơn phần tử giữa: Tương tự, target (nếu tồn tại) chỉ có thể nằm ở nửa bên phải của phần tử giữa. Ta loại bỏ nửa bên trái và tiếp tục tìm kiếm trên nửa bên phải.
4. Lặp lại quá trình này cho đến khi tìm thấy target hoặc phạm vi tìm kiếm trở nên rỗng (không còn phần tử nào để kiểm tra), lúc đó target không tồn tại trong tập hợp.

Ưu điểm:

• Cực kỳ hiệu quả: Đặc biệt với các tập hợp dữ liệu lớn.

Nhược điểm:

• Yêu cầu dữ liệu phải được sắp xếp: Nếu dữ liệu chưa sắp xếp, ta cần phải sắp xếp trước, điều này có thể tốn kém (thời gian sắp xếp thường là O(n log n)).

Độ phức tạp thời gian (Time Complexity):

• Độ phức tạp của Tìm kiếm Nhị phân là O(log n).

Tại sao lại là O(log n)?

Mỗi bước trong thuật toán Tìm kiếm Nhị phân đều loại bỏ khoảng một nửa số phần tử còn lại trong phạm vi tìm kiếm. Ví dụ:

• Bắt đầu với n phần tử.
• Sau bước 1: còn lại n/2 phần tử.
• Sau bước 2: còn lại (n/2)/2 = n/4 phần tử.
• Sau bước k: còn lại n / (2^k) phần tử.

Quá trình dừng lại khi chỉ còn 1 phần tử hoặc không còn phần tử nào. Để tìm kiếm xong, số bước k cần thiết là khi n / (2^k) xấp xỉ 1, tức là 2^k xấp xỉ n. Suy ra k xấp xỉ log₂(n). Do đó, độ phức tạp là O(log n).

Sự khác biệt giữa O(n) và O(log n) là rất lớn khi n lớn. Ví dụ, với n = 1 triệu:

• O(n) có thể cần tới 1 triệu phép so sánh.
• O(log n) (với log cơ số 2 của 1 triệu khoảng 20) chỉ cần khoảng 20 phép so sánh!

Ứng dụng thực tế của Tìm kiếm Nhị phân:

Tìm kiếm Nhị phân là xương sống của nhiều ứng dụng cần tìm kiếm nhanh trên dữ liệu có thứ tự:

• Tìm kiếm từ trong từ điển: Các từ được sắp xếp theo thứ tự bảng chữ cái.
• Tìm kiếm trang trong cuốn sách: Các trang được sắp xếp theo số thứ tự.
• Tìm kiếm một giá trị trong cơ sở dữ liệu đã được lập chỉ mục (indexed database): Index thường được tổ chức theo cấu trúc cây (như B-tree) cho phép tìm kiếm hiệu quả tương tự logarit.
• Hàm std::binary_search, std::lower_bound, std::upper_bound trong Thư viện Chuẩn C++ (STL): Các hàm này đều dựa trên nguyên lý Tìm kiếm Nhị phân và yêu cầu range (phạm vi) đầu vào phải được sắp xếp.
• Tìm kiếm một bản ghi trong file dữ liệu đã được sắp xếp.
• Trong các thuật toán khác: Ví dụ, trong thuật toán sắp xếp Merge Sort hoặc Quick Sort, việc tìm điểm phân hoạch hoặc vị trí chèn có thể tận dụng ý tưởng nhị phân.

Ví dụ minh họa bằng C++ (Phiên bản lặp):

Chúng ta sẽ sử dụng một mảng (hoặc vector) đã được sắp xếp.

#include <iostream>
#include <vector>
#include <algorithm> // Để sử dụng std::sort nếu cần (trong ví dụ này, chúng ta giả sử đã sắp xếp)

// Hàm thực hiện Tìm kiếm Nhị phân (phiên bản lặp)
// arr: vector chứa dữ liệu ĐÃ ĐƯỢC SẮP XẾP
// target: giá trị cần tìm
// Trả về chỉ mục của target nếu tìm thấy, ngược lại trả về -1
int binarySearchIterative(const std::vector<int>& arr, int target) {
    int left = 0; // Chỉ mục bắt đầu phạm vi tìm kiếm
    int right = arr.size() - 1; // Chỉ mục kết thúc phạm vi tìm kiếm

    // Lặp lại quá trình tìm kiếm cho đến khi phạm vi tìm kiếm còn hợp lệ (left <= right)
    while (left <= right) {
        // Tính chỉ mục giữa. Sử dụng công thức này để tránh tràn số với số lớn
        int mid = left + (right - left) / 2;

        // Kiểm tra phần tử tại chỉ mục giữa
        if (arr[mid] == target) {
            // Nếu tìm thấy, trả về chỉ mục mid
            return mid;
        }

        // Nếu target lớn hơn phần tử giữa, target chỉ có thể nằm ở nửa bên phải
        else if (target > arr[mid]) {
            // Di chuyển chỉ mục left sang phải của mid để tìm kiếm ở nửa bên phải
            left = mid + 1;
        }

        // Nếu target nhỏ hơn phần tử giữa, target chỉ có thể nằm ở nửa bên trái
        else { // target < arr[mid]
            // Di chuyển chỉ mục right sang trái của mid để tìm kiếm ở nửa bên trái
            right = mid - 1;
        }
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy, trả về -1
    return -1;
}

int main() {
    // Vector ĐÃ ĐƯỢC SẮP XẾP
    std::vector<int> mySortedVector = {5, 8, 10, 15, 23, 30, 42, 50};
    // Nếu vector chưa sắp xếp, bạn cần gọi:
    // std::sort(mySortedVector.begin(), mySortedVector.end());

    int target1 = 23; // Giá trị cần tìm có trong vector
    int target2 = 100; // Giá trị cần tìm không có trong vector
    int target3 = 5;  // Giá trị đầu tiên
    int target4 = 50; // Giá trị cuối cùng

    // Tìm kiếm các giá trị
    int result1 = binarySearchIterative(mySortedVector, target1);
    int result2 = binarySearchIterative(mySortedVector, target2);
    int result3 = binarySearchIterative(mySortedVector, target3);
    int result4 = binarySearchIterative(mySortedVector, target4);


    if (result1 != -1) {
        std::cout << "Tim thay " << target1 << " tai chi muc: " << result1 << " (Vector: " << mySortedVector[result1] << ")" << std::endl;
    } else {
        std::cout << target1 << " khong ton tai trong vector." << std::endl;
    }

    if (result2 != -1) {
         std::cout << "Tim thay " << target2 << " tai chi muc: " << result2 << " (Vector: " << mySortedVector[result2] << ")" << std::endl;
    } else {
        std::cout << target2 << " khong ton tai trong vector." << std::endl;
    }

     if (result3 != -1) {
        std::cout << "Tim thay " << target3 << " tai chi muc: " << result3 << " (Vector: " << mySortedVector[result3] << ")" << std::endl;
    } else {
        std::cout << target3 << " khong ton tai trong vector." << std::endl;
    }

     if (result4 != -1) {
        std::cout << "Tim thay " << target4 << " tai chi muc: " << result4 << " (Vector: " << mySortedVector[result4] << ")" << std::endl;
    } else {
        std::cout << target4 << " khong ton tai trong vector." << std::endl;
    }


    return 0;
}

Giải thích code:

1. Hàm binarySearchIterative nhận vào một vector<int> (đã sắp xếp) và target.
2. Chúng ta khởi tạo hai biến left và right để đánh dấu phạm vi tìm kiếm hiện tại, ban đầu là toàn bộ vector (từ chỉ mục 0 đến size - 1).
3. Vòng lặp while (left <= right) tiếp tục chừng nào phạm vi tìm kiếm còn hợp lệ (chỉ mục trái không vượt quá chỉ mục phải).
4. Bên trong vòng lặp, chúng ta tính chỉ mục mid. Công thức left + (right - left) / 2 được ưa dùng hơn (left + right) / 2 để tránh khả năng tràn số nếu left và right quá lớn.
5. Ta so sánh arr[mid] với target.
   • Nếu bằng, chúng ta đã tìm thấy và trả về mid.
   • Nếu target lớn hơn arr[mid], nghĩa là target chỉ có thể nằm ở bên phải của mid. Do đó, ta cập nhật left = mid + 1 để phạm vi tìm kiếm tiếp theo bắt đầu ngay sau mid.
   • Nếu target nhỏ hơn arr[mid], nghĩa là target chỉ có thể nằm ở bên trái của mid. Do đó, ta cập nhật right = mid - 1 để phạm vi tìm kiếm tiếp theo kết thúc ngay trước mid.
6. Nếu vòng lặp kết thúc (khi left > right), phạm vi tìm kiếm đã trở nên rỗng, tức là target không tồn tại, và hàm trả về -1.
7. Hàm main tạo một vector đã sắp xếp và gọi binarySearchIterative với các giá trị target khác nhau để kiểm tra cả trường hợp tìm thấy và không tìm thấy, bao gồm cả phần tử đầu và cuối.

Ví dụ minh họa bằng C++ (Phiên bản đệ quy):

Tìm kiếm Nhị phân cũng rất thích hợp để cài đặt bằng đệ quy do tính chất "chia để trị" của nó.

#include <iostream>
#include <vector>

// Hàm đệ quy thực hiện Tìm kiếm Nhị phân
// arr: vector chứa dữ liệu ĐÃ ĐƯỢC SẮP XẾP
// left: chỉ mục bắt đầu phạm vi tìm kiếm hiện tại
// right: chỉ mục kết thúc phạm vi tìm kiếm hiện tại
// target: giá trị cần tìm
// Trả về chỉ mục của target nếu tìm thấy, ngược lại trả về -1
int binarySearchRecursive(const std::vector<int>& arr, int left, int right, int target) {
    // Điều kiện dừng: Nếu phạm vi tìm kiếm không còn hợp lệ (left > right)
    if (left > right) {
        return -1; // Không tìm thấy target
    }

    // Tính chỉ mục giữa
    int mid = left + (right - left) / 2;

    // Kiểm tra phần tử tại chỉ mục giữa
    if (arr[mid] == target) {
        // Nếu tìm thấy, trả về chỉ mục mid
        return mid;
    }

    // Nếu target lớn hơn phần tử giữa, đệ quy tìm kiếm ở nửa bên phải
    else if (target > arr[mid]) {
        return binarySearchRecursive(arr, mid + 1, right, target);
    }

    // Nếu target nhỏ hơn phần tử giữa, đệ quy tìm kiếm ở nửa bên trái
    else { // target < arr[mid]
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

int main() {
    // Vector ĐÃ ĐƯỢC SẮP XẾP
    std::vector<int> mySortedVector = {5, 8, 10, 15, 23, 30, 42, 50};
    int n = mySortedVector.size();

    int target1 = 30; // Giá trị cần tìm có trong vector
    int target2 = 77; // Giá trị cần tìm không có trong vector

    // Gọi hàm đệ quy, ban đầu tìm kiếm trên toàn bộ vector (từ 0 đến n-1)
    int result1 = binarySearchRecursive(mySortedVector, 0, n - 1, target1);
    int result2 = binarySearchRecursive(mySortedVector, 0, n - 1, target2);


    if (result1 != -1) {
        std::cout << "Tim thay " << target1 << " tai chi muc: " << result1 << " (Vector: " << mySortedVector[result1] << ")" << std::endl;
    } else {
        std::cout << target1 << " khong ton tai trong vector." << std::endl;
    }

    if (result2 != -1) {
         std::cout << "Tim thay " << target2 << " tai chi muc: " << result2 << " (Vector: " << mySortedVector[result2] << ")" << std::endl;
    } else {
        std::cout << target2 << " khong ton tai trong vector." << std::endl;
    }

    return 0;
}

Giải thích code (Phiên bản đệ quy):

1. Hàm binarySearchRecursive có thêm hai tham số left và right để xác định phạm vi tìm kiếm hiện tại trong lần gọi đệ quy.
2. Điều kiện dừng (Base Case): if (left > right) là điều kiện để hàm đệ quy dừng lại. Nếu chỉ mục trái vượt quá chỉ mục phải, điều đó có nghĩa là phạm vi tìm kiếm đã co lại thành rỗng mà không tìm thấy mục tiêu, nên ta trả về -1.
3. Phần còn lại của hàm tương tự như phiên bản lặp: tính mid, so sánh arr[mid] với target.
4. Nếu tìm thấy (arr[mid] == target), trả về mid.
5. Nếu không tìm thấy ngay tại mid, thay vì cập nhật left hoặc right và tiếp tục vòng lặp, ta thực hiện gọi đệ quy chính hàm binarySearchRecursive với phạm vi tìm kiếm mới:
   • Nếu target > arr[mid], gọi đệ quy với phạm vi (mid + 1, right).
   • Nếu target < arr[mid], gọi đệ quy với phạm vi (left, mid - 1).
6. Hàm main gọi hàm đệ quy lần đầu với phạm vi toàn bộ vector (0 đến n-1).

Cả hai phiên bản lặp và đệ quy của Tìm kiếm Nhị phân đều có độ phức tạp thời gian O(log n). Phiên bản đệ quy thường ngắn gọn hơn nhưng có thể tiêu tốn bộ nhớ Stack cho các lần gọi hàm, trong khi phiên bản lặp thì không.

3. Lựa chọn giữa Tìm kiếm Tuần tự và Tìm kiếm Nhị phân

Vậy, khi nào nên dùng thuật toán nào?

• Sử dụng Tìm kiếm Tuần tự khi:
  • Tập dữ liệu nhỏ.
  • Tập dữ liệu không được sắp xếp và chi phí sắp xếp lại là không đáng hoặc không khả thi.
• Sử dụng Tìm kiếm Nhị phân khi:
  • Tập dữ liệu lớn.
  • Tập dữ liệu đã được sắp xếp hoặc chi phí sắp xếp ban đầu nhỏ hơn đáng kể so với tổng thời gian tìm kiếm (nếu có nhiều lần tìm kiếm trên cùng một tập dữ liệu).

Trong thực tế, với các tập dữ liệu lớn và nhu cầu tìm kiếm nhanh, việc duy trì dữ liệu dưới dạng đã được sắp xếp (hoặc sử dụng các cấu trúc dữ liệu khác hỗ trợ tìm kiếm nhanh như cây tìm kiếm nhị phân, bảng băm - sẽ học ở các bài sau) và sử dụng Tìm kiếm Nhị phân (hoặc các thuật toán dựa trên nguyên tắc tương tự) là cách tiếp cận phổ biến và hiệu quả.

Bài tập ví dụ:

Dãy con có độ dài tối đa

Trong một dự án xử lý dữ liệu, FullHouse Dev được giao nhiệm vụ phân tích một mảng số nguyên. Họ cần tìm ra một dãy con có độ dài lớn nhất sao cho hiệu của bất kỳ cặp phần tử nào trong dãy con đó không vượt quá 10.

Bài toán

Cho một mảng \(A\) gồm \(N\) số nguyên. Một dãy con của mảng được gọi là tốt nếu hiệu tuyệt đối của mọi cặp phần tử trong dãy con đó không vượt quá 10.

Nhiệm vụ của bạn là xác định độ dài lớn nhất có thể của một dãy con tốt.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa mảng \(A\) gồm \(N\) số nguyên.

OUTPUT FORMAT:

• In ra độ dài lớn nhất có thể của dãy con tốt.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ:

INPUT

10
4 5 10 101 2 129 131 130 118 14

OUTPUT

4

Giải thích:

• Dãy con [4, 5, 10, 14] là một dãy con tốt và có độ dài lớn nhất.
• Hiệu tuyệt đối của mọi cặp phần tử trong dãy con này đều không vượt quá 10.
• Do đó, đáp án là 4. Đây là hướng dẫn giải bài toán "Dãy con có độ dài tối đa" một cách ngắn gọn:

1. Quan sát điều kiện: Điều kiện của dãy con tốt là hiệu tuyệt đối của mọi cặp phần tử không vượt quá 10. Điều này tương đương với việc hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy con đó không vượt quá 10. max(dãy_con) - min(dãy_con) <= 10.

2. Lợi ích của việc sắp xếp: Nếu một tập hợp các số thỏa mãn điều kiện max - min <= 10, thì khi các số đó được sắp xếp, chúng sẽ nằm gần nhau trong mảng đã sắp xếp (trong một đoạn có độ dài không quá 10). Việc sắp xếp mảng ban đầu A giúp gom các phần tử có giá trị gần nhau lại.

3. Chuyển bài toán: Sau khi sắp xếp mảng A, bài toán trở thành tìm một dãy con liên tục (subarray) dài nhất trong mảng đã sắp xếp sao cho hiệu giữa phần tử cuối cùng và phần tử đầu tiên của dãy con đó không vượt quá 10. Độ dài của dãy con liên tục này chính là độ dài lớn nhất của dãy con tốt cần tìm trong mảng ban đầu.

4. Giải pháp cho mảng đã sắp xếp: Sử dụng kỹ thuật cửa sổ trượt (sliding window) hoặc hai con trỏ.

   • Duy trì một cửa sổ [left, right] trên mảng đã sắp xếp.
   • Mở rộng cửa sổ về bên phải (tăng right).
   • Tại mỗi bước, kiểm tra xem cửa sổ hiện tại [left, right] có thỏa mãn điều kiện A[right] - A[left] <= 10 không.
   • Nếu không thỏa mãn (A[right] - A[left] > 10), co cửa sổ từ bên trái (tăng left) cho đến khi điều kiện được thỏa mãn lại hoặc left vượt quá right.
   • Độ dài của cửa sổ hợp lệ hiện tại là right - left + 1. Cập nhật độ dài lớn nhất tìm được.

5. Các bước thực hiện:

   • Đọc input N và mảng A.
   • Sắp xếp mảng A theo thứ tự tăng dần.
   • Khởi tạo hai con trỏ left = 0, maxLength = 0.
   • Duyệt con trỏ right từ 0 đến N-1.
   • Bên trong vòng lặp duyệt right, sử dụng một vòng lặp while để tăng left miễn là A[right] - A[left] > 10.
   • Sau khi vòng lặp while kết thúc, cửa sổ [left, right] hiện tại là hợp lệ. Cập nhật maxLength = max(maxLength, right - left + 1).
   • Sau khi duyệt hết right, giá trị maxLength là kết quả cần tìm.

Làm thêm nhiều bài tập miễn phí tại đây