Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 프로그램으로 시작 값과 끝 값이 같은 최대 합 부분 배열 찾기

양의 정수로만 이루어진 크기 n의 배열 arr[]가 주어졌을 때, 시작 인덱스와 끝 인덱스의 값이 서로 같은 부분 배열(subarray) 중에서 원소의 합이 최대가 되는 경우를 찾는 것이 이 문제의 목표입니다.

문제 설명

찾고자 하는 부분 배열은 시작 인덱스 i와 끝 인덱스 j에서 arr[i] = arr[j]를 만족해야 합니다. 즉, 부분 배열의 첫 번째 원소와 마지막 원소가 동일해야 하며, 이 조건을 만족하는 모든 부분 배열 중 합이 가장 큰 것을 구하면 됩니다.

입력 예제

arr[] = {2, 1, 3, 5, 6, 2, 4, 3}

출력

23

설명

같은 값으로 시작하고 끝나는 부분 배열은 다음과 같습니다.

{2, 1, 3, 5, 6, 2} → 2 + 1 + 3 + 5 + 6 + 2 = 19
{3, 5, 6, 2, 4, 3} → 3 + 5 + 6 + 2 + 4 + 3 = 23

이 중 합이 가장 큰 값은 23이므로 정답은 23입니다.

풀이 접근 방법

이 문제의 핵심은 배열의 모든 원소가 양수라는 점입니다. 양수로만 이루어진 배열에서는 부분 배열의 길이가 길어질수록 합도 커집니다. 따라서 특정 값으로 시작하고 끝나는 부분 배열 중에서는 그 값이 처음 등장하는 위치(가장 왼쪽)부터 마지막에 등장하는 위치(가장 오른쪽)까지의 구간 합이 가장 큽니다.

이 성질을 이용하면 다음 순서로 문제를 해결할 수 있습니다.

  1. 접두사 합(prefix sum) 배열을 만들어 임의 구간의 합을 O(1)에 계산할 수 있도록 준비합니다.
  2. 해시 맵(unordered_map)에 각 값의 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 기록합니다.
  3. 모든 값에 대해 [첫 등장 위치, 마지막 등장 위치] 구간의 합을 계산하고, 그중 최댓값을 반환합니다.

C++ 구현 예제

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

// 시작 값과 끝 값이 같은 부분 배열 중 최대 합을 구하는 함수
int maxValue(int arr[], int n) {
    unordered_map<int, int> startIndex, endIndex; // 값별 첫/마지막 등장 인덱스
    int sumArr[n];                                // 접두사 합 배열
    sumArr[0] = arr[0];

    for (int i = 1; i < n; i++) {
        sumArr[i] = sumArr[i - 1] + arr[i];
    }

    // 각 값의 가장 왼쪽 / 오른쪽 등장 위치 기록
    for (int i = 0; i < n; i++) {
        if (startIndex.find(arr[i]) == startIndex.end())
            startIndex[arr[i]] = i;
        endIndex[arr[i]] = i;
    }

    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int left = startIndex[arr[i]];
        int right = endIndex[arr[i]];
        int rangeSum = sumArr[right] - (left > 0 ? sumArr[left - 1] : 0);
        maxSum = max(maxSum, rangeSum);
    }
    return maxSum;
}

int main() {
    int arr[] = { 2, 1, 3, 5, 6, 2, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "시작 값과 끝 값이 같은 최대 합 부분 배열의 합: "
         << maxValue(arr, n);
    return 0;
}

실행 결과

시작 값과 끝 값이 같은 최대 합 부분 배열의 합: 23

복잡도 분석

시간 복잡도: O(n) — 배열을 상수 번 순회하며 각 단계가 선형 시간 안에 처리됩니다.

공간 복잡도: O(n) — 접두사 합 배열과 해시 맵에 최대 n개의 정보를 저장합니다.

정리

배열의 원소가 모두 양수라는 조건 덕분에 '긴 부분 배열일수록 합이 커진다'는 관찰 하나만으로 브루트포스 방식(O(n²))의 탐색을 O(n) 알고리즘으로 개선할 수 있었습니다. 해시 맵으로 각 값의 경계 인덱스를 관리하고, 접두사 합으로 구간합을 빠르게 계산하는 이 패턴은 다양한 배열 문제에서 응용되는 핵심 기법이므로 꼭 기억해 두시기 바랍니다.