C++로 특정 요소를 제외한 최대 부분 배열 합 구하기

문제 소개

이 튜토리얼에서는 특정 요소를 제외한 최대 부분 배열 합(Maximum Subarray Sum Excluding Certain Elements)을 구하는 프로그램을 다룹니다.

문제의 조건은 다음과 같습니다. 크기가 각각 N과 M인 두 개의 배열 A와 B가 주어집니다. 이때 배열 A에서 부분 배열(sub-array)을 찾아야 하는데, 해당 부분 배열에 포함된 어떤 요소도 배열 B에는 존재해서는 안 되며, 동시에 부분 배열의 합이 가능한 한 최대가 되어야 합니다.

접근 방식

이 문제는 유명한 카데인 알고리즘(Kadane's Algorithm)을 응용하여 효율적으로 해결할 수 있습니다. 기본 아이디어는 다음과 같습니다.

• 배열 A의 각 요소를 순회하면서, 현재 요소가 배열 B에 존재하는지 확인합니다.
• 만약 배열 B에 존재하는 요소라면, 현재까지의 부분 배열 합을 0으로 초기화하여 해당 지점에서 부분 배열을 끊습니다.
• 배열 B에 없는 요소라면, 기존 카데인 알고리즘처럼 '현재 요소 단독'과 '현재까지 누적합 + 현재 요소' 중 더 큰 값을 선택하며 최댓값을 갱신합니다.

예제 코드

#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;
}

출력 결과

The Maximum Subarray Sum = 7

코드 설명

위 예제에서 배열 A는 {3, 4, 5, -4, 6}이고, 제외해야 할 요소를 담은 배열 B는 {1, 8, 5}입니다. 배열 A에서 값 5는 배열 B에 포함되어 있으므로 부분 배열에 사용할 수 없습니다.

따라서 후보가 되는 부분 배열은 {3, 4}, {-4, 6}, {6} 등입니다. 이중 합이 가장 큰 것은 {3, 4}로 합이 7이 되며, 이것이 곧 정답입니다.

시간 복잡도

현재 구현에서는 배열 B에 요소가 있는지 확인하기 위해 선형 탐색(linear search)을 사용하므로 전체 시간 복잡도는 O(N × M)입니다. 만약 배열 B를 먼저 정렬한 뒤 이진 탐색(binary search)을 활용하거나, 해시 세트(unordered_set)를 사용하면 시간 복잡도를 O(N + M)까지 개선할 수 있습니다.