최대 부분 배열 합 (Maximum Subarray)

정의

최대 부분 배열 합 (Maximum Subarray) 은 배열에서 연속한 구간의 합 중 최댓값을 찾는 문제.

예: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 최대 구간 [4, -1, 2, 1], 합 6.

Kadane’s Algorithm (1984, Jay Kadane) 이 O(N) 에 해결. DP / 그리디의 고전 예제.

문제 상황과 동기

길이 N 배열에서 연속 구간 합의 최댓값을 구한다.

• naive: 모든 구간 O(N^2) 탐색, 각 구간 합 O(N) → O(N^3). N=10^4 불가.
• prefix sum: 구간 합 O(1) → O(N^2). N=10^5 불가.
• Kadane: O(N) 한 패스. DP 또는 그리디로 해석 가능.

핵심 통찰: 현재까지 합이 음수면 버리고 새로 시작. 지금까지의 누적이 도움이 안 되면 현재 원소부터 다시.

PS: 최대 수익 구간 (stock profit), 이미지 처리 (1D signal), 센서 데이터 이상 탐지.

시각화

핵심 아이디어

current_sum = i번 원소를 끝으로 하는 최대 합.

current_sum = max(a[i], current_sum + a[i])
max_sum = max(max_sum, current_sum)

invariant: 현재까지의 합이 음수면 다음 원소부터 새로 시작하는 게 무조건 유리.

DP 관점:

dp[i] = i번 원소를 끝으로 하는 최대 부분 배열 합
dp[i] = max(a[i], dp[i-1] + a[i])
answer = max(dp[0..N-1])

그리디 관점:

음수 누적은 버린다. 양수 누적만 유지.

알고리즘

kadane(a):
    current_sum = a[0]
    max_sum = a[0]
    for i = 1..N-1:
        current_sum = max(a[i], current_sum + a[i])
        max_sum = max(max_sum, current_sum)
    return max_sum

구현

// Kadane's algorithm O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<long long> a(n);
  for (auto& v : a) cin >> v;
  long long curr = a[0], maxSum = a[0];
  for (int i = 1; i < n; i++) {
      curr = max(a[i], curr + a[i]);
      maxSum = max(maxSum, curr);
  }
  cout << maxSum << "\n";
}

# Kadane's algorithm O(N)
import sys
input = sys.stdin.readline
​
n = int(input())
a = list(map(int, input().split()))
curr = a[0]
max_sum = a[0]
for i in range(1, n):
  curr = max(a[i], curr + a[i])
  max_sum = max(max_sum, curr)
print(max_sum)

// Kadane's algorithm O(N)
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      long curr = 0, maxSum = Long.MIN_VALUE;
      for (int i = 0; i < n; i++) {
          long x = Long.parseLong(st.nextToken());
          curr = Math.max(x, curr + x);
          maxSum = Math.max(maxSum, curr);
      }
      System.out.println(maxSum);
  }
}

9
-2 1 -3 4 -1 2 1 -5 4

6

3
-5 -2 -8

-2

4
1 2 3 4

10

복잡도

변형 / 활용

구간 인덱스 복원

최대 합 구간의 [start, end] 를 같이 추적.

int start = 0, end = 0, temp_start = 0;
long long curr = a[0], maxSum = a[0];
for (int i = 1; i < n; i++) {
    if (curr + a[i] < a[i]) {
        curr = a[i];
        temp_start = i;
    } else {
        curr += a[i];
    }
    if (curr > maxSum) {
        maxSum = curr;
        start = temp_start;
        end = i;
    }
}

최대 / 최소 구간 곱 (Maximum Product Subarray)

곱셈은 음수 × 음수 = 양수. max_prod, min_prod 동시 추적.

long long maxProd = a[0], minProd = a[0], ans = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] < 0) swap(maxProd, minProd);
    maxProd = max(a[i], maxProd * a[i]);
    minProd = min(a[i], minProd * a[i]);
    ans = max(ans, maxProd);
}

환형 배열 (Circular Array)

배열이 환형 (끝과 시작이 연결). 최댓값은:

1. 일반 Kadane 결과
2. 전체 합 - (최소 부분 배열 합)

둘 중 큰 것.

2D 최대 부분 행렬 합

각 열 구간을 고정, 행을 압축해서 1D Kadane. O(N^2 M) 또는 O(N M^2).

for top = 0..N-1:
  col_sum[0..M-1] = 0
  for bottom = top..N-1:
    for j = 0..M-1:
      col_sum[j] += matrix[bottom][j]
    max_sum = max(max_sum, kadane(col_sum))

함정

1. 모두 음수일 때

모두 음수면 가장 큰 하나를 선택. Kadane 은 자동으로 처리 (max(a[i], curr + a[i])).

2. long long / overflow

N=10^5, 원소 최대 10^4 → 합 10^9. C++ int 범위 벗어날 수 있음.

3. 빈 부분 배열 허용 여부

문제에 따라 “빈 구간 (합 0)” 허용 여부 다름. 허용하면 max_sum = max(0, kadane_result).

4. 구간 인덱스 복원

단순 max 값만 구하면 O(1) 공간. 구간 복원은 start/end 추적 필요.

BOJ 연습 문제

참고

• 동적 계획법
• 누적 합