C++에서 시작 값과 끝 값이 같은 최대 합 부분 배열 찾기

이 튜토리얼에서는 시작 값과 끝 값이 동일한 최대 합 부분 배열(subarray)을 찾는 프로그램을 다룹니다.

정수로 이루어진 배열이 하나 주어지며, 우리의 목표는 양쪽 끝에 위치한 두 요소의 값이 서로 같으면서 그 합이 최대가 되는 부분 배열을 찾는 것입니다.

접근 방식

이 문제는 누적 합(prefix sum)과 해시 맵(unordered_map)을 함께 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 전체적인 알고리즘의 흐름은 다음과 같습니다.

1. 배열의 각 인덱스까지의 누적 합을 미리 계산해 저장합니다.
2. 각 값이 처음 등장하는 인덱스(first)와 마지막으로 등장하는 인덱스(last)를 해시 맵에 기록합니다.
3. 모든 요소를 순회하면서 '첫 등장 인덱스부터 마지막 등장 인덱스까지'의 구간 합을 누적 합의 차로 계산하고, 그중 최댓값을 정답으로 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
//최대 합을 구하는 함수
int maxValue(int a[], int n) {
   unordered_map<int, int> first, last;
   int pr[n];
   pr[0] = a[0];
   for (int i = 1; i < n; i++) {
      pr[i] = pr[i - 1] + a[i];
      if (first[a[i]] == 0)
         first[a[i]] = i;
      last[a[i]] = i;
   }
   int ans = 0;
   for (int i = 0; i < n; i++) {
      int start = first[a[i]];
      int end = last[a[i]];
      ans = max(ans, pr[end] - pr[start - 1]);
   }
   return ans;
}
int main() {
   int arr[] = { 1, 3, 5, 2, 4, 18, 2, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << maxValue(arr, n);
   return 0;
}

출력

37

결과 설명

배열 { 1, 3, 5, 2, 4, 18, 2, 3 }에서 값 3은 인덱스 1과 인덱스 7에 위치합니다. 따라서 인덱스 1부터 7까지의 구간 합(3 + 5 + 2 + 4 + 18 + 2 + 3 = 37)이 시작 값과 끝 값이 같은 부분 배열 중에서 가장 큰 합이 됩니다.

복잡도 분석

시간 복잡도: O(n) — 배열을 몇 번만 순회하면 되므로 매우 효율적입니다.
공간 복잡도: O(n) — 누적 합 배열과 해시 맵을 저장하기 위한 추가 메모리가 필요합니다.