Tìm tổng mảng con lớn nhất loại trừ các phần tử nhất định trong C++

Trong bài toán này, chúng ta được cung cấp hai mảng arr1[] kích thước n và arr2[] kích thước m. Nhiệm vụ là viết chương trình tìm tổng mảng con lớn nhất loại trừ các phần tử nhất định.

Mô tả bài toán

Chúng ta cần tìm tổng mảng con lớn nhất từ các phần tử của mảng arr1[] mà không xuất hiện trong arr2[].

Ví dụ minh họa

Đầu vào

arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}

Đầu ra

9

Giải thích

arr1 sau khi loại bỏ phần tử của arr2[] = {4, 5}
Cả hai có thể tạo thành mảng con, nên tổng = 4+5 = 9.

Phương pháp giải

Cách đơn giản: sử dụng thuật toán Kadane để tìm tất cả các dãy con dương liên tiếp. Tìm tổng các phần tử của dãy con này và trả về lớn nhất. Cập nhật thuật toán dựa trên việc không xét các phần tử của arr2. Tìm kiếm phần tử bằng thuật toán tìm kiếm. Nếu có trong arr2, xóa cửa sổ hiện tại và đặt lại. Kiểm tra nếu tổng nhỏ hơn maxSum, cập nhật maxSum = sum.

Chương trình minh họa (Cách 1 - Tìm kiếm nhị phân)

#include <iostream>
using namespace std;

int isInArr2(int arr2[], int start, int end, int searchEle) {
    if (end >= start) {
        int mid = start + (end - start) / 2;
        if (arr2[mid] == searchEle)
            return true;
        if (arr2[mid] > searchEle)
            return isInArr2(arr2, start, mid - 1, searchEle);
        return isInArr2(arr2, mid + 1, end, searchEle);
    }
    return false;
}

int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m) {
    int maxSum = -1, sum = 0;
    for (int i = 0; i < n; i++) {
        if (isInArr2(arr2, 0, m, arr1[i])) {
            sum = 0;
            continue;
        }
        sum = max(arr1[i], sum + arr1[i]);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main() {
    int arr1[] = { 5, 4, 7, 2, 9 };
    int arr2[] = { 1, 9, 2, 7 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Tổng mảng con lớn nhất loại trừ các phần tử nhất định là "
         << calcMaxSubArraySum(arr1, arr2, n, m);
    return 0;
}

Đầu ra

Tổng mảng con lớn nhất loại trừ các phần tử nhất định là 9

Cách này hiệu quả nhưng có thể tốt hơn bằng cách dùng map để kiểm tra sự hiện diện của phần tử trong mảng thứ hai, tiết kiệm thời gian tính toán.

Chương trình minh họa (Cách 2 - Sử dụng unordered_map)

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

int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m) {
    unordered_map<int, int> checkVal;
    for (int i = 0; i < m; i++)
        checkVal[arr2[i]] = 1;
    
    int maxSum = -1, sum = 0;
    for (int i = 0; i < n; i++) {
        if (checkVal[arr1[i]] == 1) {
            sum = 0;
            continue;
        }
        sum = max(arr1[i], sum + arr1[i]);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main() {
    int arr1[] = { 5, 4, 7, 2, 9 };
    int arr2[] = { 1, 9, 2, 7 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Tổng mảng con lớn nhất loại trừ các phần tử nhất định là "
         << calcMaxSubArraySum(arr1, arr2, n, m);
    return 0;
}

Đầu ra

Tổng mảng con lớn nhất loại trừ các phần tử nhất định là 9