Thuật toán Chia để trị (Divide and Conquer) trong C++ (Full Code)

Thuật toán Chia để trị (Divide and Conquer) là một kỹ thuật thiết kế thuật toán quan trọng và mạnh mẽ, được sử dụng để giải quyết nhiều loại bài toán. Ý tưởng chính của thuật toán Chia để trị là chia một bài toán lớn thành các bài toán con nhỏ hơn, giải quyết các bài toán con này, và sau đó kết hợp kết quả lại để có được kết quả cho bài toán lớn ban đầu. Dưới đây là các bước cơ bản của thuật toán Chia để trị:

1. Chia (Divide): Chia bài toán lớn thành các bài toán con nhỏ hơn. Quá trình này tiếp tục cho đến khi các bài toán con đủ nhỏ để giải quyết trực tiếp.

2. Trị (Conquer): Giải quyết từng bài toán con. Nếu các bài toán con đủ nhỏ, chúng có thể được giải quyết trực tiếp. Nếu không, thuật toán Chia để trị sẽ được áp dụng đệ quy để tiếp tục chia các bài toán con thành các bài toán nhỏ hơn nữa.

3. Kết hợp (Combine): Kết hợp các kết quả từ các bài toán con để có được kết quả cho bài toán ban đầu.

Một số thuật toán và bài toán nổi tiếng sử dụng kỹ thuật Chia để trị bao gồm:

1. Merge Sort: Là một thuật toán sắp xếp với độ phức tạp thời gian là O(n log n). Merge Sort chia mảng cần sắp xếp thành hai nửa, sắp xếp từng nửa một cách đệ quy và sau đó kết hợp hai nửa đã được sắp xếp lại.

2. Quicksort: Là một thuật toán sắp xếp khác với độ phức tạp trung bình là O(n log n). Quicksort chọn một phần tử làm “chốt” (pivot) và chia mảng thành hai phần: phần nhỏ hơn chốt và phần lớn hơn chốt. Sau đó, nó sắp xếp hai phần này một cách đệ quy.

3. Binary Search: Là một thuật toán tìm kiếm trong mảng đã sắp xếp với độ phức tạp thời gian là O(log n). Binary Search chia mảng thành hai nửa và so sánh giá trị cần tìm với phần tử ở giữa. Dựa trên kết quả so sánh, nó sẽ tiếp tục tìm kiếm trong một nửa phù hợp.

4. Closest Pair of Points: Là một bài toán trong hình học tính toán, tìm cặp điểm gần nhau nhất trong một tập hợp các điểm trên mặt phẳng. Bài toán này có thể được giải quyết hiệu quả bằng cách sử dụng kỹ thuật Chia để trị.

5. Matrix Multiplication (Strassen’s Algorithm): Là một thuật toán để nhân hai ma trận với độ phức tạp thấp hơn O(n³) bằng cách chia các ma trận thành các ma trận con nhỏ hơn.

6. Maximum Subarray Sum: Được sử dụng để tìm dãy con có tổng lớn nhất trong một mảng.

Ưu điểm của thuật toán Chia để trị:

– Giảm độ phức tạp của bài toán lớn bằng cách chia nó thành các bài toán con nhỏ hơn.

– Thường hiệu quả hơn các thuật toán không chia để trị khi giải quyết các bài toán phức tạp.

– Tận dụng tính đệ quy để giải quyết các bài toán con độc lập.

Nhược điểm của thuật toán Chia để trị:

– Một số bài toán có thể không phù hợp để áp dụng thuật toán Chia để trị.

– Có thể tốn nhiều bộ nhớ do sử dụng tính đệ quy và lưu trữ các bài toán con.

Một số ví dụ:

1. Tìm kiếm nhị phân (Binary Search)

Khái niệm:

Tìm kiếm nhị phân áp dụng trên mảng đã sắp xếp.
Chia mảng làm hai phần, so sánh phần tử giữa với giá trị cần tìm:
- Nếu phần tử giữa nhỏ hơn giá trị cần tìm, tìm kiếm trong nửa phải.
- Nếu lớn hơn, tìm kiếm trong nửa trái.
Độ phức tạp: O(logn)

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // Không tìm thấy
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target = 7;
    int index = binarySearch(arr, target);
    if (index != -1) std::cout << "Found at index: " << index << std::endl;
    else std::cout << "Not found" << std::endl;
    return 0;
}

2. Sắp xếp trộn (Merge Sort)

Khái niệm:

Sắp xếp mảng bằng cách chia nhỏ thành các phần tử riêng lẻ, sau đó trộn chúng lại theo thứ tự.
Độ phức tạp: O(nlogn).

Code tham khảo:

#include <iostream>
#include <vector>

void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    for (int num : arr) std::cout << num << " ";
    return 0;
}

3. Sắp xếp nhanh (Quick Sort)

Khái niệm:

Chọn một phần tử làm pivot và phân chia mảng thành hai phần:
- Phần nhỏ hơn pivot.
- Phần lớn hơn pivot.
Tiếp tục áp dụng đệ quy cho từng phần.
Độ phức tạp trung bình: O(nlogn).

Code tham khảo:

#include <iostream>
#include <vector>

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) std::cout << num << " ";
    return 0;
}

4. Bài toán dãy con lớn nhất (Maximum Subarray Problem)

Tìm dãy con liên tiếp có tổng lớn nhất.
Giải bằng cách chia để trị:
- Tìm giá trị lớn nhất ở nửa trái.
- Tìm giá trị lớn nhất ở nửa phải.
- Tìm giá trị lớn nhất bắt buộc phải qua giữa.
Độ phức tạp: O(nlogn).

Code tham khảo:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Hàm tính tổng lớn nhất của mảng con cắt qua điểm giữa
int maxCrossingSum(const vector<int>& arr, int left, int mid, int right) {
    int sum = 0, leftSum = INT_MIN, rightSum = INT_MIN;

    // Tính tổng lớn nhất từ mid về phía trái
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        leftSum = max(leftSum, sum);
    }

    sum = 0; // Reset sum

    // Tính tổng lớn nhất từ mid + 1 về phía phải
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        rightSum = max(rightSum, sum);
    }

    return leftSum + rightSum;
}

// Hàm đệ quy tìm tổng lớn nhất của mảng con
int maxSubArray(const vector<int>& arr, int left, int right) {
    // Trường hợp cơ sở: chỉ có một phần tử
    if (left == right) return arr[left];

    // Chia mảng thành hai nửa
    int mid = left + (right - left) / 2;

    // Tìm tổng lớn nhất trong nửa trái, nửa phải và cắt qua giữa
    int leftMax = maxSubArray(arr, left, mid);
    int rightMax = maxSubArray(arr, mid + 1, right);
    int crossMax = maxCrossingSum(arr, left, mid, right);

    // Trả về giá trị lớn nhất trong ba trường hợp
    return max(leftMax, max(rightMax, crossMax));
}

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

    // Kiểm tra mảng không rỗng
    if (arr.empty()) {
        cout << "Array is empty!" << endl;
        return 0;
    }

    // Tính tổng lớn nhất của mảng con
    int maxSum = maxSubArray(arr, 0, arr.size() - 1);
    cout << "Dãy con lớn nhất: " << maxSum << endl;

    return 0;
}

5. Tìm phần tử lớn thứ k trong mảng

Sử dụng thuật toán chia để trị tương tự Quick Sort.
Chọn pivot và phân chia:
- Nếu pivot là phần tử lớn thứ k: Trả về.
- Nếu k nhỏ hơn: Tìm ở nửa trái.
- Nếu k lớn hơn: Tìm ở nửa phải.
Độ phức tạp: O(n) trung bình.

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

int kthLargest(std::vector<int>& arr, int left, int right, int k) {
    int pivot = arr[right], i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] >= pivot) {
            std::swap(arr[i], arr[j]);
            i++;
        }
    }
    std::swap(arr[i], arr[right]);

    int count = i - left + 1;
    if (count == k) return arr[i];
    if (count > k) return kthLargest(arr, left, i - 1, k);
    return kthLargest(arr, i + 1, right, k - count);
}

int main() {
    std::vector<int> arr = {3, 2, 1, 5, 6, 4};
    int k = 2;
    std::cout << "Kth largest element: " << kthLargest(arr, 0, arr.size() - 1, k) << std::endl;
    return 0;
}

Các bài tập ứng dụng:

Bài toán 1. Bạn là một nhà đầu tư cổ phiếu và muốn phân tích lợi nhuận hàng ngày từ một chuỗi ngày nhất định. Mỗi ngày, bạn có thể lãi (số dương) hoặc lỗ (số âm). Bài toán yêu cầu bạn tìm ra khoảng thời gian liên tục nào mang lại lợi nhuận lớn nhất.

Ví dụ. Giả sử bạn có bảng lợi nhuận hằng ngày sau đây (tính bằng triệu đồng):

Ngày: 1 2 3 4 5 6 7 8 9

Lợi nhuận: -2 1 -3 4 -1 2 1 -5 4

Khoảng ngày nào giúp bạn đạt được lợi nhuận lớn nhất? Lợi nhuận lớn nhất là bao nhiêu?

Đầu vào: Một mảng chứa các số nguyên (lợi nhuận mỗi ngày).

Ví dụ: [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Kết quả:

Lợi nhuận lớn nhất: 6.
Khoảng ngày đạt lợi nhuận lớn nhất: Từ ngày 4 đến ngày 7.

Tổng lợi nhuận = 4 + (-1) + 2 + 1 = 6.

Phân tích thuật toán Chia để trị:

Chia mảng thành hai phần:
1. Tính lợi nhuận lớn nhất ở nửa trái.
1. Tính lợi nhuận lớn nhất ở nửa phải.
1. Tính lợi nhuận lớn nhất qua giữa.
Kết hợp các kết quả:
1. Giá trị lớn nhất trong ba phần trên chính là kết quả.

Ví dụ:

Chia nhỏ mảng:
1. Chia [-2, 1, -3, 4, -1, 2, 1, -5, 4] thành hai phần:
  1. Trái: [-2, 1, -3, 4]
  1. Phải: [-1, 2, 1, -5, 4].
2. Tính dãy con lớn nhất:
  1. Nửa trái ([-2, 1, -3, 4]): Lợi nhuận lớn nhất = 4.
  1. Nửa phải ([-1, 2, 1, -5, 4]): Lợi nhuận lớn nhất = 4.
  1. Qua giữa (4, -1, 2, 1): Lợi nhuận lớn nhất = 6.
3. Kết quả cuối cùng:
  1. Giá trị lớn nhất trong ba kết quả trên là 6

Code tham khảo:

#include <iostream>
#include <vector>
#include <climits>

// Hàm tính lợi nhuận lớn nhất qua điểm giữa
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    int leftSum = INT_MIN, sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        leftSum = std::max(leftSum, sum);
    }

    int rightSum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        rightSum = std::max(rightSum, sum);
    }

    return leftSum + rightSum;
}

// Hàm đệ quy chia để trị
int maxSubArray(const std::vector<int>& arr, int left, int right) {
    if (left == right) return arr[left];

    int mid = left + (right - left) / 2;

    int leftMax = maxSubArray(arr, left, mid);
    int rightMax = maxSubArray(arr, mid + 1, right);
    int crossMax = maxCrossingSum(arr, left, mid, right);

    return std::max({leftMax, rightMax, crossMax});
}

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

    // Tính lợi nhuận lớn nhất
    int maxProfit = maxSubArray(profits, 0, profits.size() - 1);

    std::cout << "Lợi nhuận lớn nhất: " << maxProfit << std::endl;

    return 0;
}

Bài tập 2. Lợi nhuận của cổ phiếu

Bạn có một mảng số nguyên đại diện cho lợi nhuận hoặc lỗ hàng ngày từ việc đầu tư cổ phiếu. Hãy tìm lợi nhuận lớn nhất mà bạn có thể đạt được từ một khoảng thời gian liên tiếp.

Ví dụ:

Đầu vào: [-3, 2, -1, 4, -2, 3, -5, 4]
Kết quả: 7 (từ đoạn [2, -1, 4, -2, 3]).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm lợi nhuận lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm lợi nhuận lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về lợi nhuận lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

int main() {
    std::vector<int> arr = {-3, 2, -1, 4, -2, 3, -5, 4};
    int n = arr.size();
    int max_sum = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Lợi nhuận lớn nhất là: " << max_sum << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm lợi nhuận lớn nhất trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị lợi nhuận hoặc lỗ hàng ngày và gọi hàm maxSubArraySum để tìm lợi nhuận lớn nhất.

Bài tập 3. Tối ưu hóa sản xuất

Bạn là quản lý của một nhà máy, và bạn có dữ liệu hiệu suất sản xuất theo từng giờ trong ngày (số dương biểu thị tăng trưởng, số âm biểu thị suy giảm). Hãy xác định khoảng thời gian liên tiếp nào có hiệu suất cao nhất, cùng với giá trị hiệu suất.

Ví dụ:

Đầu vào: [1, -2, 3, 10, -4, 7, 2, -5]
Kết quả: 18 (từ đoạn [3, 10, -4, 7, 2]).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm hiệu suất lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm hiệu suất lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về hiệu suất lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

int main() {
    std::vector<int> arr = {1, -2, 3, 10, -4, 7, 2, -5};
    int n = arr.size();
    int max_sum = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Hiệu suất lớn nhất là: " << max_sum << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm hiệu suất lớn nhất trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị hiệu suất theo từng giờ trong ngày và gọi hàm maxSubArraySum để tìm hiệu suất lớn nhất.

Bài tập 4. Đánh giá đội bóng

Một đội bóng ghi được điểm trong một số trận đấu liên tiếp (điểm có thể dương hoặc âm, biểu thị thắng hoặc thua). Hãy tìm khoảng liên tiếp của các trận đấu có điểm số cao nhất.

Ví dụ:

Đầu vào: [5, -7, 3, 9, -2, 6, -1, -4]
Kết quả mong muốn: 16 (từ đoạn [3, 9, -2, 6]).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm điểm số lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm điểm số lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về điểm số lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

int main() {
    std::vector<int> arr = {5, -7, 3, 9, -2, 6, -1, -4};
    int n = arr.size();
    int max_sum = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Điểm số cao nhất là: " << max_sum << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm điểm số lớn nhất trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị điểm số từ các trận đấu và gọi hàm maxSubArraySum để tìm điểm số cao nhất.

Bài tập 5. Chuỗi tín hiệu

Bạn đang xử lý dữ liệu tín hiệu từ một cảm biến. Các giá trị tín hiệu có thể âm hoặc dương, biểu thị cường độ dao động. Hãy tìm đoạn tín hiệu liên tiếp có tổng giá trị cường độ lớn nhất.

Ví dụ:

Đầu vào: [-1, -2, 4, -1, 2, 1, -5, 4]
Kết quả: 6 (từ đoạn [4, -1, 2, 1]).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm tổng giá trị cường độ lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm tổng giá trị cường độ lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về tổng giá trị cường độ lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

int main() {
    std::vector<int> arr = {-1, -2, 4, -1, 2, 1, -5, 4};
    int n = arr.size();
    int max_sum = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Tổng giá trị cường độ lớn nhất là: " << max_sum << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm tổng giá trị cường độ lớn nhất trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị tín hiệu và gọi hàm maxSubArraySum để tìm tổng giá trị cường độ lớn nhất.

Bài tập 6. Dãy con dài nhất tổng lớn nhất

Tìm tổng lớn nhất của một dãy con liên tiếp, đồng thời xuất ra dãy con đó.

Ví dụ:

Đầu vào: [2, -8, 3, -2, 4, -10]
Kết quả:
- Tổng lớn nhất: 5
- Dãy con: [3, -2, 4].

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm trả về tổng và mảng con với tổng lớn nhất qua điểm giữa
std::tuple<int, std::vector<int>> maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    int max_left = mid;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    int max_right = mid + 1;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = i;
        }
    }

    std::vector<int> subArray(arr.begin() + max_left, arr.begin() + max_right + 1);
    return {left_sum + right_sum, subArray};
}

// Hàm đệ quy tìm tổng và mảng con với tổng lớn nhất trong mảng con [left, right]
std::tuple<int, std::vector<int>> maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return {arr[left], {arr[left]}};
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Tìm tổng và mảng con lớn nhất ở các đoạn trái, phải, và qua giữa
    auto [left_sum, left_subArray] = maxSubArraySum(arr, left, mid);
    auto [right_sum, right_subArray] = maxSubArraySum(arr, mid + 1, right);
    auto [cross_sum, cross_subArray] = maxCrossingSum(arr, left, mid, right);

    // Tìm tổng lớn nhất trong các trường hợp và trả về kết quả tương ứng
    if (left_sum >= right_sum && left_sum >= cross_sum) {
        return {left_sum, left_subArray};
    } else if (right_sum >= left_sum && right_sum >= cross_sum) {
        return {right_sum, right_subArray};
    } else {
        return {cross_sum, cross_subArray};
    }
}

int main() {
    std::vector<int> arr = {2, -8, 3, -2, 4, -10};
    int n = arr.size();
    auto [max_sum, max_subArray] = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Tổng lớn nhất: " << max_sum << std::endl;
    std::cout << "Dãy con: ";
    for (int num : max_subArray) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất và trả về dãy con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm tổng lớn nhất và dãy con trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị và gọi hàm maxSubArraySum để tìm tổng lớn nhất cùng với dãy con tương ứng.

Bài tập 7. Tối ưu hóa doanh số

Bạn quản lý một cửa hàng và ghi lại số tiền lãi (hoặc lỗ) hàng ngày trong tháng. Tìm chuỗi ngày liên tiếp có doanh thu ròng lớn nhất.

Ví dụ:

Đầu vào: [4, -1, 2, 1, -5, 4]
Kết quả mong muốn: 6 (từ đoạn [4, -1, 2, 1]).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm tổng doanh thu lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm tổng doanh thu lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về tổng doanh thu lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

int main() {
    std::vector<int> arr = {4, -1, 2, 1, -5, 4};
    int n = arr.size();
    int max_sum = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Tổng doanh thu lớn nhất là: " << max_sum << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm tổng doanh thu lớn nhất trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị lãi hoặc lỗ hàng ngày và gọi hàm maxSubArraySum để tìm tổng doanh thu lớn nhất.

Bài tập 8. Ứng dụng thời tiết

Bạn ghi lại sự biến động nhiệt độ trong một tuần (giá trị dương thể hiện tăng nhiệt độ, giá trị âm thể hiện giảm nhiệt độ). Hãy xác định khoảng thời gian liên tiếp nào có tổng nhiệt độ thay đổi cao nhất.

Ví dụ:

Đầu vào: [1, -3, 2, 1, -1, 3, -2]
Kết quả: 5 (từ đoạn [2, 1, -1, 3]).

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm tổng biến động nhiệt độ lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm tổng biến động nhiệt độ lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về tổng biến động nhiệt độ lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

int main() {
    std::vector<int> arr = {1, -3, 2, 1, -1, 3, -2};
    int n = arr.size();
    int max_sum = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Tổng biến động nhiệt độ lớn nhất là: " << max_sum << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm tổng biến động nhiệt độ lớn nhất trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị biến động nhiệt độ và gọi hàm maxSubArraySum để tìm tổng biến động nhiệt độ lớn nhất.

Bài tập 9. Nhiều mảng nhỏ

Bạn được cho một danh sách gồm n mảng con, mỗi mảng có các số nguyên. Tính tổng lớn nhất cho mỗi mảng con và trả về kết quả.

Ví dụ:

Mảng 1: [1, -3, 2, 1, -1]

Mảng 2: [4, -1, 2, 1, -5]

Mảng 3: [-2, 1, -3, 4, -1]

Kết quả: [3, 6, 4]

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm tìm tổng lớn nhất trong khoảng thời gian liên tiếp sử dụng thuật toán Chia để trị
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
        }
    }

    // Tổng lớn nhất của mảng con băng qua mid
    return left_sum + right_sum;
}

// Hàm đệ quy tìm tổng lớn nhất trong mảng con [left, right]
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return arr[left];
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Trả về tổng lớn nhất trong các trường hợp: trái, phải, hoặc qua giữa
    return std::max({ maxSubArraySum(arr, left, mid),
                      maxSubArraySum(arr, mid + 1, right),
                      maxCrossingSum(arr, left, mid, right) });
}

// Hàm tìm tổng lớn nhất cho từng mảng con trong danh sách
std::vector<int> findMaxSums(const std::vector<std::vector<int>>& arrays) {
    std::vector<int> results;
    for (const auto& arr : arrays) {
        int max_sum = maxSubArraySum(arr, 0, arr.size() - 1);
        results.push_back(max_sum);
    }
    return results;
}

int main() {
    std::vector<std::vector<int>> arrays = {
        {1, -3, 2, 1, -1},
        {4, -1, 2, 1, -5},
        {-2, 1, -3, 4, -1}
    };
    
    std::vector<int> max_sums = findMaxSums(arrays);

    std::cout << "Tổng lớn nhất cho mỗi mảng con: ";
    for (int sum : max_sums) {
        std::cout << sum << " ";
    }
    std::cout << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm tổng lớn nhất trong mảng con từ left đến right.
Hàm findMaxSums thực hiện tính tổng lớn nhất cho từng mảng con trong danh sách arrays.
Trong hàm main, chúng ta tạo một danh sách các mảng con arrays và gọi hàm findMaxSums để tìm tổng lớn nhất cho từng mảng con và in ra kết quả.

Bài tập 10. Phân tích dãy con lớn nhất

Cho một dãy số nguyên dài bất kỳ, bạn cần tính:

Tổng lớn nhất của dãy con liên tiếp.
Độ dài của dãy con đạt tổng lớn nhất.
Chỉ số bắt đầu và kết thúc của dãy con trong mảng ban đầu.

Ví dụ:

Đầu vào: [3, -1, -1, 4, -1, 2, 1, -5, 4]
Kết quả:
- Tổng lớn nhất: 6
- Độ dài: 4
- Vị trí bắt đầu: 3 (chỉ số 0-based)
- Vị trí kết thúc: 6.

Code tham khảo:

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

// Hàm trả về tổng, độ dài và chỉ số bắt đầu, kết thúc của mảng con với tổng lớn nhất qua điểm giữa
std::tuple<int, int, int, int> maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    // Tính tổng lớn nhất từ mid về bên trái
    int sum = 0;
    int left_sum = INT_MIN;
    int max_left = mid;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) {
            left_sum = sum;
            max_left = i;
        }
    }

    // Tính tổng lớn nhất từ mid+1 về bên phải
    sum = 0;
    int right_sum = INT_MIN;
    int max_right = mid + 1;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = i;
        }
    }

    int total_sum = left_sum + right_sum;
    int length = max_right - max_left + 1;
    return {total_sum, length, max_left, max_right};
}

// Hàm đệ quy trả về tổng, độ dài và chỉ số bắt đầu, kết thúc của mảng con với tổng lớn nhất trong mảng con [left, right]
std::tuple<int, int, int, int> maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    // Nếu chỉ có một phần tử
    if (left == right) {
        return {arr[left], 1, left, left};
    }

    // Tìm điểm giữa
    int mid = (left + right) / 2;

    // Tìm tổng, độ dài và chỉ số bắt đầu, kết thúc của mảng con lớn nhất ở các đoạn trái, phải, và qua giữa
    auto [left_sum, left_length, left_start, left_end] = maxSubArraySum(arr, left, mid);
    auto [right_sum, right_length, right_start, right_end] = maxSubArraySum(arr, mid + 1, right);
    auto [cross_sum, cross_length, cross_start, cross_end] = maxCrossingSum(arr, left, mid, right);

    // Tìm tổng lớn nhất trong các trường hợp và trả về kết quả tương ứng
    if (left_sum >= right_sum && left_sum >= cross_sum) {
        return {left_sum, left_length, left_start, left_end};
    } else if (right_sum >= left_sum && right_sum >= cross_sum) {
        return {right_sum, right_length, right_start, right_end};
    } else {
        return {cross_sum, cross_length, cross_start, cross_end};
    }
}

int main() {
    std::vector<int> arr = {3, -1, -1, 4, -1, 2, 1, -5, 4};
    int n = arr.size();
    auto [max_sum, length, start_index, end_index] = maxSubArraySum(arr, 0, n - 1);

    std::cout << "Tổng lớn nhất: " << max_sum << std::endl;
    std::cout << "Độ dài: " << length << std::endl;
    std::cout << "Vị trí bắt đầu: " << start_index << std::endl;
    std::cout << "Vị trí kết thúc: " << end_index << std::endl;

    return 0;
}

Trong đoạn mã này:

Hàm maxCrossingSum tính tổng lớn nhất, độ dài và chỉ số bắt đầu, kết thúc của mảng con băng qua điểm giữa mid.
Hàm maxSubArraySum sử dụng thuật toán Chia để trị để tìm tổng lớn nhất, độ dài và chỉ số bắt đầu, kết thúc của mảng con trong mảng con từ left đến right.
Trong hàm main, chúng ta tạo một vector arr với các giá trị và gọi hàm maxSubArraySum để tìm tổng lớn nhất cùng với độ dài và chỉ số bắt đầu, kết thúc của mảng con tương ứng.

CHÚC CÁC BẠN HỌC TỐT1

Lập trình C/C++

Thuật toán Chia để trị (Divide and Conquer) trong C++ (Full Code)

Đỗ Thành