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

Mô tả bài toán

Cho hai mảng A (kích thước N) và B (kích thước M). Tìm mảng con liên tiếp trong A có tổng lớn nhất, với điều kiện không phần tử nào trong mảng con nằm trong B.

Giải pháp (Kadane biến thể)

• Duyệt mảng A, nếu A[i] nằm trong B → reset tổng hiện tại = 0, bỏ qua.
• Ngược lại, áp dụng Kadane: curr_max = max(A[i], curr_max + A[i]), cập nhật max_so_far.
• Kiểm tra tồn tại trong B bằng tìm kiếm tuyến tính (hoặc dùng set để O(1)).

Ví dụ minh họa

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

bool isPresent(int B[], int m, int x) {
    for (int i = 0; i < m; i++) if (B[i] == x) return true;
    return false;
}

int findMaxSubarraySumUtil(int A[], int B[], int n, int m) {
    int max_so_far = INT_MIN, curr_max = 0;
    for (int i = 0; i < n; i++) {
        if (isPresent(B, m, A[i])) { curr_max = 0; continue; }
        curr_max = max(A[i], curr_max + A[i]);
        max_so_far = max(max_so_far, curr_max);
    }
    return max_so_far;
}

void findMaxSubarraySum(int A[], int B[], int n, int m) {
    int maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m);
    if (maxSubarraySum == INT_MIN) cout << "Maximum Subarray Sum cant be found" << endl;
    else cout << "The Maximum Subarray Sum = " << maxSubarraySum << endl;
}

int main() {
    int A[] = {3, 4, 5, -4, 6};
    int B[] = {1, 8, 5};
    int n = sizeof(A) / sizeof(A[0]);
    int m = sizeof(B) / sizeof(B[0]);
    findMaxSubarraySum(A, B, n, m);
    return 0;
}

Đầu ra

The Maximum Subarray Sum = 7