Bài 24.2: Bài toán tối ưu trên mảng 1 chiều trong C++

Chào mừng các bạn đã quay trở lại với series học C++ của FullhouseDev!

Trong các bài học trước, chúng ta đã làm quen với cấu trúc dữ liệu mảng 1 chiều, cách khai báo, truy cập và thực hiện các thao tác cơ bản như duyệt mảng, tìm kiếm tuyến tính, sắp xếp đơn giản. Tuy nhiên, thế giới của mảng 1 chiều còn rộng lớn hơn rất nhiều, đặc biệt là khi chúng ta đứng trước các bài toán tối ưu.

Bài toán tối ưu trên mảng 1 chiều không đơn giản chỉ là tìm một giá trị, mà là tìm kiếm một cấu trúc (một phần tử, một dãy con, một cặp phần tử,...) thỏa mãn một điều kiện nào đó và làm cho một hàm mục tiêu đạt giá trị tốt nhất (lớn nhất hoặc nhỏ nhất). Đây là loại bài toán rất phổ biến trong lập trình thi đấu, phỏng vấn kỹ thuật, và cả trong các ứng dụng thực tế yêu cầu hiệu năng cao.

Việc giải quyết hiệu quả các bài toán này đòi hỏi chúng ta phải suy nghĩ sâu hơn về cấu trúc dữ liệu và tìm ra các thuật toán thông minh, tránh các cách tiếp cận "ngây thơ" (naive) thường có độ phức tạp thời gian rất cao.

Hãy cùng bắt tay vào khám phá một số bài toán tối ưu kinh điển trên mảng 1 chiều và xem C++ giúp chúng ta giải quyết chúng như thế nào nhé!

1. Tìm Phần Tử Lớn Nhất/Nhỏ Nhất và Vị Trí

Đây là bài toán cơ bản nhất, nhưng nó đặt nền móng cho ý tưởng giữ lại giá trị tốt nhất đã gặp.

Bài toán: Cho một mảng các số nguyên, tìm phần tử có giá trị lớn nhất và chỉ số của nó.

Cách tiếp cận: Duyệt qua mảng một lần. Giữ một biến max_val để lưu trữ giá trị lớn nhất tìm được cho đến hiện tại, và một biến max_idx để lưu chỉ số của phần tử đó. Ban đầu, gán max_val bằng phần tử đầu tiên và max_idx bằng 0. Khi duyệt, nếu gặp một phần tử lớn hơn max_val, cập nhật cả max_val và max_idx.

Code minh họa:

#include <iostream>
#include <vector>
#include <limits> // Dùng cho numeric_limits

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};

    if (arr.empty()) {
        cout << "Mang rong, khong co phan tu nao." << endl;
        return 0;
    }

    int max_val = numeric_limits<int>::min(); // Khởi tạo min để đảm bảo phần tử đầu tiên được chọn
    int max_idx = -1; // Khởi tạo chỉ số không hợp lệ

    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] > max_val) {
            max_val = arr[i];
            max_idx = i;
        }
    }

    cout << "Phan tu lon nhat: " << max_val << endl;
    cout << "Tai chi so: " << max_idx << endl;

    return 0;
}

Giải thích Code:

Chúng ta sử dụng vector<int> để biểu diễn mảng, rất linh hoạt.
numeric_limits<int>::min() là cách an toàn để khởi tạo max_val với giá trị nhỏ nhất có thể của kiểu int, đảm bảo phần tử đầu tiên của mảng (hoặc bất kỳ phần tử nào) sẽ lớn hơn nó và được chọn làm max_val ban đầu.
Vòng lặp for duyệt qua từng phần tử của vector.
Câu lệnh if (arr[i] > max_val) so sánh phần tử hiện tại với giá trị lớn nhất đã tìm được.
Nếu lớn hơn, chúng ta cập nhật max_val bằng arr[i] và max_idx bằng chỉ số i hiện tại.
Độ phức tạp thời gian: O(N), với N là số phần tử trong mảng, vì chúng ta chỉ duyệt mảng một lần.

2. Bài Toán Tổng Dãy Con Liên Tục Lớn Nhất (Maximum Subarray Sum)

Đây là một bài toán kinh điển và là ví dụ tuyệt vời về sự khác biệt giữa thuật toán ngây thơ và thuật toán tối ưu.

Bài toán: Cho một mảng các số nguyên (có thể âm), tìm tổng lớn nhất của một dãy con liên tục (không rỗng) của mảng đó.

Ví dụ: Với mảng {-2, 1, -3, 4, -1, 2, 1, -5, 4}, dãy con liên tục có tổng lớn nhất là {4, -1, 2, 1} với tổng là 6.

Cách tiếp cận ngây thơ: Duyệt qua tất cả các dãy con liên tục có thể có. Có O(N^2) dãy con liên tục. Với mỗi dãy con, tính tổng (mất O(N) trong trường hợp tệ nhất). Tổng cộng là O(N^3). Chúng ta có thể cải tiến việc tính tổng dãy con bằng cách tính tổng trước (prefix sum) hoặc tính trực tiếp trong vòng lặp ngoài, giảm xuống O(N^2). Tuy nhiên, O(N^2) vẫn chưa phải là tối ưu.

Cách tiếp cận tối ưu (Kadane's Algorithm): Đây là một thuật toán quy hoạch động đơn giản nhưng mạnh mẽ, chạy trong O(N). Ý tưởng là duyệt qua mảng một lần, duy trì hai biến:

current_max: Tổng lớn nhất của dãy con kết thúc tại vị trí hiện tại.
global_max: Tổng lớn nhất của dãy con tìm được trên toàn bộ mảng cho đến hiện tại.

Tại mỗi vị trí i, current_max mới sẽ là max(arr[i], current_max + arr[i]). Nếu arr[i] lớn hơn current_max + arr[i], điều đó có nghĩa là bắt đầu một dãy con mới tại arr[i] sẽ tốt hơn là mở rộng dãy con trước đó. global_max sẽ được cập nhật là max(global_max, current_max).

Code minh họa (Kadane's Algorithm):

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho max
#include <limits>    // Dùng cho numeric_limits

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

    if (arr.empty()) {
        cout << "Mang rong, tong lon nhat la 0 (hoac tuy quy dinh)." << endl;
        return 0; // Tùy vào định nghĩa bài toán (có được chọn dãy con rỗng không)
    }

    int current_max = arr[0]; // Tổng lớn nhất kết thúc tại vị trí hiện tại
    int global_max = arr[0];  // Tổng lớn nhất tìm được trên toàn bộ mảng

    // Lưu ý: Cần xử lý trường hợp mảng chỉ có 1 phần tử hoặc tất cả âm
    // Cách khởi tạo global_max = arr[0] và lặp từ i=1 xử lý được điều này

    for (size_t i = 1; i < arr.size(); ++i) {
        current_max = max(arr[i], current_max + arr[i]);
        global_max = max(global_max, current_max);
    }

    cout << "Tong day con lien tuc lon nhat: " << global_max << endl;

    return 0;
}

Giải thích Code:

Chúng ta khởi tạo cả current_max và global_max bằng phần tử đầu tiên arr[0]. Điều này quan trọng để xử lý đúng các trường hợp mảng có một phần tử hoặc tất cả các phần tử đều âm.
Vòng lặp bắt đầu từ phần tử thứ hai (i = 1).
Tại mỗi bước, current_max được cập nhật: nó là giá trị lớn hơn giữa:
- Chính phần tử arr[i] (bắt đầu một dãy con mới tại đây).
- Tổng của phần tử arr[i] cộng với current_max trước đó (mở rộng dãy con cũ).
global_max được cập nhật bằng giá trị lớn hơn giữa global_max hiện tại và current_max. current_max luôn là ứng viên cho global_max.
Cuối cùng, global_max chứa tổng lớn nhất của bất kỳ dãy con liên tục nào.
Độ phức tạp thời gian: O(N), vì chúng ta chỉ duyệt mảng một lần. Đây là sự cải tiến đáng kể so với O(N^2) hoặc O(N^3).

3. Tìm Cặp Chỉ Số (i, j) Với j > i Sao Cho arr[j] - arr[i] Là Lớn Nhất

Bài toán này yêu cầu tìm hiệu lớn nhất giữa hai phần tử, với điều kiện phần tử thứ hai nằm sau phần tử thứ nhất trong mảng.

Bài toán: Cho một mảng các số nguyên, tìm giá trị lớn nhất của arr[j] - arr[i] với j > i.

Ví dụ: Với mảng {7, 1, 5, 3, 6, 4}, kết quả là 6 - 1 = 5 (tại i=1, j=4).

Cách tiếp cận ngây thơ: Duyệt qua tất cả các cặp (i, j) thỏa mãn j > i và tính hiệu arr[j] - arr[i], giữ lại hiệu lớn nhất. Cách này mất O(N^2).

Cách tiếp cận tối ưu: Duyệt qua mảng một lần. Tại mỗi vị trí j, chúng ta muốn tìm arr[i] nhỏ nhất đã gặp trước đó (với i < j) để làm cho hiệu arr[j] - arr[i] là lớn nhất. Chúng ta duy trì một biến min_so_far lưu trữ giá trị nhỏ nhất của các phần tử từ arr[0] đến arr[j-1]. Khi duyệt đến arr[j], hiệu lớn nhất có thể kết thúc tại j là arr[j] - min_so_far. Chúng ta cập nhật hiệu lớn nhất tổng thể (max_diff) và sau đó cập nhật min_so_far bằng min(min_so_far, arr[j]) cho bước tiếp theo.

Code minh họa:

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho max, min
#include <limits>    // Dùng cho numeric_limits

int main() {
    vector<int> arr = {7, 1, 5, 3, 6, 4};

    if (arr.size() < 2) {
        cout << "Mang can it nhat 2 phan tu." << endl;
        return 0;
    }

    int min_so_far = arr[0]; // Gia tri nho nhat da gap cho den vi tri hien tai (i < j)
    int max_diff = arr[1] - arr[0]; // Khoi tao hieu lon nhat bang cap dau tien

    // Bắt đầu duyệt từ phần tử thứ 2 (chỉ số 1)
    for (size_t j = 1; j < arr.size(); ++j) {
        // Cập nhật hiệu lớn nhất có thể kết thúc tại vị trí j
        // max_diff = max(max_diff, arr[j] - min_so_far); // Cách này sai, cần kiểm tra trước khi cập nhật min_so_far

        // Cách đúng: Tìm hiệu lớn nhất có thể sử dụng arr[j]
        // Hiệu lớn nhất kết thúc tại j là arr[j] trừ đi min_so_far trước arr[j]
        max_diff = max(max_diff, arr[j] - min_so_far);

        // Cập nhật min_so_far cho bước tiếp theo (bao gồm cả arr[j])
        min_so_far = min(min_so_far, arr[j]);
    }

    cout << "Hieu arr[j] - arr[i] lon nhat (j > i): " << max_diff << endl;

    return 0;
}

Giải thích Code:

Chúng ta cần ít nhất 2 phần tử trong mảng.
min_so_far được khởi tạo bằng phần tử đầu tiên arr[0].
max_diff được khởi tạo bằng hiệu của hai phần tử đầu tiên arr[1] - arr[0]. Đây là hiệu hợp lệ đầu tiên chúng ta xét.
Vòng lặp bắt đầu từ phần tử thứ hai (j = 1).
Tại mỗi vị trí j, chúng ta tính hiệu arr[j] - min_so_far. Giá trị min_so_far tại thời điểm này là giá trị nhỏ nhất trong arr[0...j-1]. Đây chính là ứng viên cho hiệu lớn nhất kết thúc tại j. Chúng ta cập nhật max_diff với giá trị lớn hơn giữa max_diff hiện tại và arr[j] - min_so_far.
Sau khi cập nhật max_diff, chúng ta cập nhật min_so_far bằng cách lấy giá trị nhỏ nhất giữa min_so_far cũ và arr[j]. Điều này đảm bảo min_so_far cho bước lặp tiếp theo (khi duyệt arr[j+1]) sẽ là giá trị nhỏ nhất trong arr[0...j].
Độ phức tạp thời gian: O(N), vì chúng ta chỉ duyệt mảng một lần.

4. Tìm Cặp Hai Phần Tử Có Tổng Bằng Một Giá Trị Cho Trước (Two Sum)

Một bài toán phỏng vấn kinh điển, cũng có thể được tối ưu trên mảng.

Bài toán: Cho một mảng các số nguyên và một giá trị mục tiêu target, tìm xem có tồn tại hai chỉ số i và j khác nhau sao cho arr[i] + arr[j] == target hay không. Nếu có, trả về một cặp chỉ số đó.

Ví dụ: Mảng [2, 7, 11, 15], target = 9. Kết quả: [0, 1] vì arr[0] + arr[1] = 2 + 7 = 9.

Cách tiếp cận ngây thơ: Sử dụng hai vòng lặp lồng nhau để kiểm tra tất cả các cặp (i, j) với i != j. Độ phức tạp O(N^2).

Cách tiếp cận tối ưu (Sử dụng Two Pointers trên mảng đã sắp xếp):

Sao chép mảng ban đầu và sắp xếp mảng sao chép đó. Ghi nhớ chỉ số ban đầu (nếu bài toán yêu cầu trả về chỉ số gốc). Việc sắp xếp mất O(N log N).
Sử dụng kỹ thuật "hai con trỏ" (Two Pointers). Đặt một con trỏ left ở đầu mảng đã sắp xếp và một con trỏ right ở cuối mảng.
Lặp lại chừng nào left < right:
- Tính tổng current_sum = sorted_arr[left] + sorted_arr[right].
- Nếu current_sum == target, chúng ta đã tìm thấy một cặp. Tìm lại chỉ số gốc trong mảng ban đầu và trả về.
- Nếu current_sum < target, tổng quá nhỏ, cần tăng giá trị. Di chuyển con trỏ left sang phải (left++).
- Nếu current_sum > target, tổng quá lớn, cần giảm giá trị. Di chuyển con trỏ right sang trái (right--).
Nếu vòng lặp kết thúc mà không tìm thấy cặp nào, trả về kết quả tương ứng (ví dụ: mảng rỗng hoặc chỉ số không hợp lệ).

Kỹ thuật Two Pointers trên mảng đã sắp xếp chạy trong O(N). Tổng cộng độ phức tạp là O(N log N) do bước sắp xếp.

Code minh họa (Sử dụng Two Pointers):

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho sort
#include <utility>   // Dùng cho pair

int main() {
    vector<int> arr = {2, 7, 11, 15};
    int target = 9;

    // Tạo vector pair lưu giá trị và chỉ số gốc
    vector<pair<int, int>> indexed_arr(arr.size());
    for (size_t i = 0; i < arr.size(); ++i) {
        indexed_arr[i] = {arr[i], i};
    }

    // Sắp xếp theo giá trị
    sort(indexed_arr.begin(), indexed_arr.end());

    int left = 0;
    int right = indexed_arr.size() - 1;
    bool found = false;
    int index1 = -1, index2 = -1;

    while (left < right) {
        int current_sum = indexed_arr[left].first + indexed_arr[right].first;

        if (current_sum == target) {
            // Tìm thấy cặp
            index1 = indexed_arr[left].second;
            index2 = indexed_arr[right].second;
            found = true;
            break; // Tìm thấy 1 cặp là đủ theo yêu cầu bài toán
        } else if (current_sum < target) {
            left++; // Cần tổng lớn hơn
        } else { // current_sum > target
            right--; // Cần tổng nhỏ hơn
        }
    }

    if (found) {
        cout << "Tim thay cap chi so (" << index1 << ", " << index2 << ") co tong bang " << target << endl;
        // Tùy yêu cầu có thể trả về mảng {index1, index2}
    } else {
        cout << "Khong tim thay cap nao co tong bang " << target << endl;
    }

    return 0;
}

Giải thích Code:

Chúng ta tạo một vector mới chứa các cặp pair<int, int>, mỗi cặp lưu trữ giá trị của phần tử và chỉ số gốc của nó trong mảng ban đầu.
Sắp xếp indexed_arr dựa trên giá trị của phần tử (thành phần .first của cặp). sort mặc định sắp xếp pair dựa trên thành phần đầu tiên.
Sử dụng hai con trỏ left và right trỏ vào đầu và cuối của indexed_arr đã sắp xếp.
Vòng lặp while (left < right) tiếp tục chừng nào hai con trỏ chưa gặp hoặc vượt qua nhau.
Tính current_sum từ giá trị tại hai con trỏ.
Dựa vào so sánh current_sum với target, chúng ta di chuyển left hoặc right để điều chỉnh tổng.
Nếu tìm thấy current_sum == target, chúng ta lấy chỉ số gốc từ thành phần .second của cặp và kết thúc.
Độ phức tạp thời gian: O(N log N) cho việc sắp xếp và O(N) cho Two Pointers, tổng là O(N log N). Độ phức tạp không gian là O(N) để lưu trữ indexed_arr.

(Lưu ý: Bài toán Two Sum cũng có thể giải trong O(N) thời gian trung bình sử dụng unordered_map (hash map) để lưu trữ target - current_value và chỉ số của nó. Cách này không cần sắp xếp nhưng dùng thêm không gian).

Comments

There are no comments at the moment.