Thuật toán Chia để trị (Divide and Conquer): mô hình 3 bước, phân biệt với QHĐ và code C++, Python

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

// Tìm tổng đoạn con liên tiếp lớn nhất trong đoạn a[lo .. hi] bằng Chia để trị O(n log n)
long long max_subarray_dac(const vector<long long>& a, int lo, int hi) {
    // Trường hợp cơ sở: đoạn chỉ có 1 phần tử
    if (lo == hi) {
        return a[lo];
    }
    int mid = lo + (hi - lo) / 2;

    // 1 & 2. Chia (Divide) và Trị (Conquer) hai nửa độc lập
    long long tot_trai = max_subarray_dac(a, lo, mid);
    long long tot_phai = max_subarray_dac(a, mid + 1, hi);

    // 3. Gộp (Combine): Tìm đoạn con tốt nhất vắt ngang qua ranh giới mid và mid + 1
    long long max_hau_to_trai = LLONG_MIN, tong_trai = 0;
    for (int i = mid; i >= lo; --i) {
        tong_trai += a[i];
        max_hau_to_trai = max(max_hau_to_trai, tong_trai);
    }

    long long max_tien_to_phai = LLONG_MIN, tong_phai = 0;
    for (int j = mid + 1; j <= hi; ++j) {
        tong_phai += a[j];
        max_tien_to_phai = max(max_tien_to_phai, tong_phai);
    }

    long long tot_giua = max_hau_to_trai + max_tien_to_phai;
    return max({tot_trai, tot_phai, tot_giua});
}

int main() {
    // Test 1: Mảng kinh điển [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> đoạn [4, -1, 2, 1] có tổng = 6
    vector<long long> a1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "MaxSub1: " << max_subarray_dac(a1, 0, (int)a1.size() - 1) << "\n";

    // Test 2: Mảng [5, 4, -1, 7, 8] -> toàn bộ mảng có tổng = 23
    vector<long long> a2 = {5, 4, -1, 7, 8};
    cout << "MaxSub2: " << max_subarray_dac(a2, 0, (int)a2.size() - 1) << "\n";

    // Test 3: Mảng toàn số âm [-8, -3, -6, -2, -5] -> chọn phần tử lớn nhất = -2
    vector<long long> a3 = {-8, -3, -6, -2, -5};
    cout << "MaxSub3: " << max_subarray_dac(a3, 0, (int)a3.size() - 1) << "\n";

    return 0;
}

def max_subarray_dac(a: list[int], lo: int, hi: int) -> int:
    """Tìm tổng đoạn con liên tiếp lớn nhất trong a[lo .. hi] bằng Chia để trị O(n log n)."""
    # Trường hợp cơ sở: đoạn chỉ có 1 phần tử
    if lo == hi:
        return a[lo]

    mid = (lo + hi) // 2

    # 1 & 2. Chia (Divide) và Trị (Conquer) hai nửa độc lập
    tot_trai = max_subarray_dac(a, lo, mid)
    tot_phai = max_subarray_dac(a, mid + 1, hi)

    # 3. Gộp (Combine): Tìm đoạn con tốt nhất vắt ngang qua mid và mid + 1
    max_hau_to_trai = a[mid]
    tong_trai = 0
    for i in range(mid, lo - 1, -1):
        tong_trai += a[i]
        if tong_trai > max_hau_to_trai:
            max_hau_to_trai = tong_trai

    max_tien_to_phai = a[mid + 1]
    tong_phai = 0
    for j in range(mid + 1, hi + 1):
        tong_phai += a[j]
        if tong_phai > max_tien_to_phai:
            max_tien_to_phai = tong_phai

    tot_giua = max_hau_to_trai + max_tien_to_phai
    return max(tot_trai, tot_phai, tot_giua)


if __name__ == "__main__":
    # Test 1: Mảng kinh điển [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> tổng = 6
    a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(f"MaxSub1: {max_subarray_dac(a1, 0, len(a1) - 1)}")

    # Test 2: Mảng [5, 4, -1, 7, 8] -> tổng = 23
    a2 = [5, 4, -1, 7, 8]
    print(f"MaxSub2: {max_subarray_dac(a2, 0, len(a2) - 1)}")

    # Test 3: Mảng toàn số âm [-8, -3, -6, -2, -5] -> tổng = -2
    a3 = [-8, -3, -6, -2, -5]
    print(f"MaxSub3: {max_subarray_dac(a3, 0, len(a3) - 1)}")

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

// Đếm số cặp (i < j) mà a[i] > a[j] trong đoạn a[lo .. hi] bằng Chia để trị O(n log n)
long long dem_cap_lon_hon_dac(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;

    // 1 & 2. Đếm đệ quy ở nửa trái và nửa phải
    long long dem = dem_cap_lon_hon_dac(a, lo, mid)
                  + dem_cap_lon_hon_dac(a, mid + 1, hi);

    // 3. Gộp hai nửa đã tăng dần và đếm các cặp vắt ngang (i ở nửa trái, j ở nửa phải)
    vector<int> tam;
    tam.reserve(hi - lo + 1);
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) {
            tam.push_back(a[i++]);
        } else {
            // Vì nửa trái đã tăng dần, mọi phần tử từ a[i .. mid] đều lớn hơn a[j]
            dem += (mid - i + 1);
            tam.push_back(a[j++]);
        }
    }
    while (i <= mid) tam.push_back(a[i++]);
    while (j <= hi) tam.push_back(a[j++]);
    for (int k = lo; k <= hi; ++k) a[k] = tam[k - lo];
    return dem;
}

int main() {
    vector<vector<int>> cac_mang = {
        {5, 1, 4, 2, 8},  // 4 cặp: (5,1), (5,4), (5,2), (4,2)
        {8, 4, 2, 1},     // 6 cặp
        {1, 3, 5, 7}      // 0 cặp
    };

    for (auto a : cac_mang) {
        cout << "Inversions: " << dem_cap_lon_hon_dac(a, 0, (int)a.size() - 1) << "\n";
    }
    return 0;
}

def dem_cap_lon_hon_dac(a: list[int], lo: int, hi: int) -> int:
    """Đếm số cặp (i < j) mà a[i] > a[j] trong đoạn a[lo .. hi] bằng Chia để trị O(n log n)."""
    if lo >= hi:
        return 0
    mid = (lo + hi) // 2

    # 1 & 2. Đếm đệ quy ở nửa trái và nửa phải
    dem = dem_cap_lon_hon_dac(a, lo, mid) + dem_cap_lon_hon_dac(a, mid + 1, hi)

    # 3. Gộp hai nửa đã tăng dần và đếm các cặp vắt ngang (i ở nửa trái, j ở nửa phải)
    tam: list[int] = []
    i, j = lo, mid + 1
    while i <= mid and j <= hi:
        if a[i] <= a[j]:
            tam.append(a[i])
            i += 1
        else:
            # Mọi phần tử từ a[i .. mid] đều lớn hơn a[j]
            dem += mid - i + 1
            tam.append(a[j])
            j += 1
    tam.extend(a[i : mid + 1])
    tam.extend(a[j : hi + 1])
    a[lo : hi + 1] = tam
    return dem


if __name__ == "__main__":
    cac_mang = [
        [5, 1, 4, 2, 8],  # 4 cặp: (5,1), (5,4), (5,2), (4,2)
        [8, 4, 2, 1],     # 6 cặp
        [1, 3, 5, 7],     # 0 cặp
    ]

    for a in cac_mang:
        b = a[:]
        print(f"Inversions: {dem_cap_lon_hon_dac(b, 0, len(b) - 1)}")