최대 부분배열 — 자리마다 최선 하나만 들고 간다

배열의 원소가 전부 양수라면 답은 뻔하다. 무엇을 더 붙여도 합이 커지니 배열 전체가 답이다. 음수가 섞이는 순간 문제가 시작된다. 어디서 끊고, 어디서 손해를 감수하고 지나갈 것인가.

---

문제

연속 부분배열은 배열에서 이웃한 원소를 통째로 잘라낸 조각이다. 배열 $a_1, a_2, \dots, a_N$ 에서 $a_i, a_{i+1}, \dots, a_j$ ($i \le j$) 꼴이면 모두 연속 부분배열이다. 이 중 원소의 합이 가장 큰 것을 찾는다. 아래에서는 연속 부분배열을 짧게 구간이라고도 부른다.

원소가 전부 양수면 고민할 것이 없다. 무엇을 더 붙여도 합이 커지므로 배열 전체가 답이다. 음수가 섞이면 달라진다.

$a = [3, -5, 2, 4, -2, 3, -6, 8]$ 을 보자. 배열 전체의 합은 $3 - 5 + 2 + 4 - 2 + 3 - 6 + 8 = 7$ 이다. 답은 7이 아니다. 앞의 $3, -5$ 를 버리고 $a_3$ 부터 끝까지 고르면 $2 + 4 - 2 + 3 - 6 + 8 = 9$ 다.

앞머리를 버린 이유는 $a_1 + a_2 = -2$ 라서다. 이 둘을 함께 끌고 가면 뒤에 오는 모든 구간이 2만큼 손해를 본다. 중간의 $-2$ 와 $-6$ 은 사정이 다르다. 8만 따로 떼어 $[8]$ 을 고를 수는 있다. 앞의 $2 + 4$ 와 8을 한 구간에 함께 담으려면 연속이라는 조건 때문에 두 음수를 반드시 지나가야 한다. 지나가는 대가를 치르고 얻은 9가 8 하나보다 크므로 감수한다.

어떤 음수는 버리고 어떤 음수는 통과하는 이 판단을 자동으로 내리는 것이 이 문제다.

---

모두 세어 보기

가장 단순한 방법은 모든 연속 부분배열을 나열하고 각각의 합을 구하는 것이다. 비용을 따지려면 후보가 몇 개인지부터 알아야 한다.

시작 위치로 세기. $a_1$ 에서 시작하는 부분배열은 끝 위치가 $a_1$ 부터 $a_N$ 까지 $N$ 개다. $a_2$ 에서 시작하면 $N-1$ 개, 계속 줄어 $a_N$ 에서 시작하면 1개다. 모두 더하면

$$N + (N-1) + \cdots + 1 = \frac{N(N+1)}{2}$$

경계로 세기. 부분배열 하나는 왼쪽 경계와 오른쪽 경계로 결정된다. 경계는 $a_1$ 앞, 원소 사이 $N-1$ 곳, $a_N$ 뒤를 합쳐 $N+1$ 개다. 서로 다른 두 곳을 고르면 부분배열 하나가 정해지므로

$$\binom{N+1}{2} = \frac{N(N+1)}{2}$$

두 셈법이 같은 값을 준다. $N = 8$ 이면 36개다.

후보 하나의 합을 처음부터 더하면 최악 $O(N)$ 이 걸린다. 후보가 $\Theta(N^2)$ 개이므로 전체는 $O(N^3)$ 이다.

---

누적합으로 $O(N^2)$

$O(N^3)$ 에 곱해진 마지막 $N$ 은 합을 매번 처음부터 다시 더해서 생긴다. 합을 미리 준비해 두면 사라진다.

누적합 $P_j$ 를 앞에서부터 $j$ 개의 합으로 정의한다.

$$P_0 = 0, \qquad P_j = a_1 + a_2 + \cdots + a_j$$

$a_i$ 부터 $a_j$ 까지의 합은 $P_j$ 에서 앞머리 $P_{i-1}$ 을 덜어낸 값이다.

$$a_i + a_{i+1} + \cdots + a_j = P_j - P_{i-1}$$

$P_0 = 0$ 을 따로 둔 이유가 여기서 나온다. $i = 1$ 일 때 덜어낼 앞머리가 없는데, $P_0 = 0$ 이 그 “비어 있음”을 대신한다. 누적합이 원소가 아니라 원소 사이의 경계에 붙는다고 보면 자연스럽다. 경계가 $N+1$ 개라는 앞 절의 셈과 같은 이야기다.

예시 배열의 누적합은 $P_0 \dots P_8 = 0,\, 3,\, -2,\, 0,\, 4,\, 2,\, 5,\, -1,\, 7$ 이다. $a_3$ 부터 $a_5$ 까지의 합을 확인하면 $P_5 - P_2 = 2 - (-2) = 4$ 이고, 직접 더한 $2 + 4 - 2 = 4$ 와 같다.

누적합을 만드는 데 한 번의 훑기, 곧 $O(N)$ 이면 된다. 그 뒤로는 후보 하나의 합이 뺄셈 한 번이다. 후보가 $\Theta(N^2)$ 개이므로 전체는 $O(N^2)$ 이고, 누적합 배열을 저장하는 공간 $O(N)$ 이 더 든다.

---

자리마다 최선 하나

$O(N^2)$ 은 후보를 여전히 전부 본다. 더 줄이려면 후보를 세는 일 자체를 그만두어야 한다.

먼저 정의를 못박는다. 빈 배열도 답으로 허용한다. 원소를 하나도 고르지 않으면 합은 0이다. 모든 원소가 음수인 배열에서 답이 0인지 가장 큰 음수인지는 이 정의가 갈라놓는다. 문제마다 조건으로 주어지며, 풀이는 거의 같다.

부분 문제는 “뒷조각”(suffix)으로 잡는다. $a_1 \dots a_i$ 까지만 떼어 놓고, 그 앞에서부터 몇 개를 더 잘라낸 뒤 남은 $a_s, \dots, a_i$ 를 뒷조각이라 부른다. 잘라내는 개수를 0개부터 $i$ 개까지 바꾸면 뒷조각이 하나씩 나오므로 뒷조각은 모두 $i+1$ 개다. $i$ 개를 전부 잘라내면 아무것도 남지 않는데, 그 빈 뒷조각도 후보에 넣는다.

$i = 4$ 로 직접 세어 보자. $a_1 \dots a_4 = [3, -5, 2, 4]$ 의 뒷조각은 다섯 개다.

잘라낸 개수	뒷조각	합
0개	$[3, -5, 2, 4]$	$4$
1개	$[-5, 2, 4]$	$1$
2개	$[2, 4]$	$6$
3개	$[4]$	$4$
4개	빈 뒷조각	$0$

가장 큰 값은 6이고, 이것이 $k_4$ 다. 표에서 보이듯 빈 것을 빼면 뒷조각은 모두 $a_i$ 에서 끝나는 구간이다. 빈 것까지 넣어야 위에서 못박은 “빈 배열도 허용” 정의와 맞아떨어진다.

각 자리마다 이 값 하나씩만 들고 다닌다. $k_1, \dots, k_N$ 을 모두 구하면 답은 그중 최댓값이다. 비어 있지 않은 부분배열은 모두 어딘가에서 끝나므로 그 자리의 뒷조각으로 한 번씩 세어지고, 빈 배열은 모든 $k_i$ 가 0 이상이라 이미 반영되어 있다.

$k_i$ 에서 $k_{i+1}$ 로 넘어가는 규칙을 보자. $x = a_{i+1}$ 이라 하자. $a_1 \dots a_{i+1}$ 의 뒷조각은 두 종류다.

• $x$ 를 포함하는 것. $a_1 \dots a_i$ 의 뒷조각 뒤에 $x$ 를 붙인 모양이다. 앞의 뒷조각이 비어 있어도 되므로 $x$ 하나짜리도 여기 들어간다. 앞에 올 수 있는 최대 합이 $k_i$ 이니, 이 종류의 최대 합은 $k_i + x$ 다.
• 빈 뒷조각. 합은 0이다.

둘 중 큰 쪽이 $k_{i+1}$ 이다.

$$k_0 = 0, \qquad k_{i+1} = \max(k_i + x,\; 0)$$

기저 $k_0$ 은 원소를 하나도 보지 않은 상태다. 빈 배열의 뒷조각은 빈 것 하나뿐이므로 $k_0 = 0$ 이다.

$k_i + x$ 가 음수면 0을 고르는 편이 낫다. 여기서 구간이 한 번 끊긴다. 지금까지 끌고 온 앞부분을 통째로 버리고 다음 자리부터 새로 시작한다는 뜻이다.

“앞부분으로 가능한 최대 합이 $k_i$” 라는 한 줄에 이 알고리즘의 정당성이 전부 들어 있다. 앞부분을 조금 손해 보게 잡으면 뒤에서 더 벌 수 있지 않을까 하는 의심은 추가 설명 — 왜 이어 붙이는 것이 최선인가에서 닫는다.

예시 배열을 훑으면 $k$ 수열은 $3,\, 0,\, 2,\, 6,\, 4,\, 7,\, 1,\, 9$ 다. $i = 2$ 에서 $k_1 + a_2 = 3 - 5 = -2$ 라 0으로 끊었고, 그 다음 자리부터 자란 구간이 $i = 8$ 에서 9에 닿는다.

코드는 값 두 개만 들고 가면 된다.

// a[0..n-1].  빈 배열을 허용하는 정의이므로 답은 항상 0 이상이다.
long long maxSubarray(const vector<int>& a) {
    long long k = 0, best = 0;   // k: 지금 자리에서 끝나는 최선, best: 지금까지의 답
    for (int x : a) {
        k = max(k + x, 0LL);     // 음수로 내려가면 앞부분을 버린다
        best = max(best, k);
    }
    return best;
}

훑기 한 번, 변수 두 개다. 시간은 $O(N)$, 공간은 $O(1)$ 이다. 누적합 배열조차 남기지 않는다.

---

빈 배열을 허용하지 않으면

원소를 최소 하나는 골라야 한다는 조건이면 정의가 바뀐다. $k_i$ 를 ”$a_1 \dots a_i$ 의 비어 있지 않은 뒷조각 중 최대 합”, 곧 $a_i$ 에서 끝나는 구간의 최대 합으로 다시 두자. 비어 있지 않은 뒷조각도 두 종류다.

• 원소가 둘 이상. 앞의 뒷조각이 비어 있지 않으므로 최대 합은 $k_i + x$ 다.
• $x$ 하나뿐. 합은 $x$ 다.

$$k_1 = a_1, \qquad k_{i+1} = \max(k_i + x,\; x)$$

0 대신 $x$ 와 비교한다는 점만 다르다. 이제 $k_i$ 가 음수일 수 있다.

// 원소를 최소 하나 고르는 정의.  a 는 비어 있지 않다고 가정한다.
long long maxSubarrayNonEmpty(const vector<int>& a) {
    long long k = a[0], best = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        k = max(k + a[i], (long long)a[i]);
        best = max(best, k);
    }
    return best;
}

정의가 항상 답을 바꾸지는 않는다. 예시 배열을 비허용 정의로 돌리면 $k$ 수열은 $3,\, -2,\, 2,\, 6,\, 4,\, 7,\, 1,\, 9$ 이고 답은 그대로 9다. 답이 양수인 배열에서는 빈 배열이 최선이 될 일이 없다. 갈라지는 것은 모든 원소가 음수일 때다. $[-3, -1, -2]$ 에서 허용하면 답이 0, 허용하지 않으면 $-1$ 이다.

---

포함하는가, 포함하지 않는가

같은 알고리즘을 다른 말로 적을 수도 있다. $a_1$ 부터 $a_i$ 까지만 본 상태에서 값 두 개를 들고 간다. 두 값 모두 범위가 앞쪽 $a_1 \dots a_i$ 로 한정된다는 점이 중요하다.

• 뒷조각 쪽: $a_1 \dots a_i$ 의 뒷조각 중 최선, 곧 $k_i$
• 이미 끝난 쪽: $a_i$ 앞에서 이미 끝난 구간의 최선, 곧 $k_1, \dots, k_{i-1}$ 의 최댓값

위 코드에서 best 는 $i$ 번째 반복에 들어설 때 정확히 두 번째 값을 들고 있다가, k 를 갱신한 뒤 $k_i$ 까지 반영해 $\max(k_1, \dots, k_i)$ 가 된다. 두 값을 나란히 적는 서술과 k·best 두 변수를 굴리는 코드는 같은 계산이다.

이 둘을 ”$a_i$ 를 포함하는 최선”과 “포함하지 않는 최선”이라 부르기도 한다. 빈 뒷조각을 허용하는 정의에서 첫 번째 값은 정확히는 ”$a_i$ 를 포함하는 최선과 0 중 큰 쪽”이다. $a_i$ 를 포함하는 후보가 모두 음수일 때만 둘이 갈리고, 그때 $k_i$ 는 0이 된다.

동적 계획법 ②는 “마지막 날에 일하는가”라는 결정 하나로 점화식을 세웠다. 여기서도 결정은 하나, “이 자리를 포함하는가”다. 결정이 깔끔하게 두 갈래로 갈리는 것은 부분 문제를 뒷조각으로 잡았기 때문이다. 부분 문제를 ”$a_1 \dots a_i$ 안에서의 답” 하나로만 잡으면 이렇게 되지 않는다. 앞의 답이 어디서 끝났는지 모르면 $a_{i+1}$ 을 이어 붙일 수 있는지 판단할 수 없다. 방금 값을 둘로 나눈 것도 뒷조각 쪽을 따로 붙잡아 두기 위해서다.

---

더 나가면

두 가지가 남았다. 하나는 $k_{i+1} = \max(k_i + x,\, 0)$ 이 왜 옳은가다. “앞부분의 최선은 $k_i$” 를 당연하게 받아들였지만, 앞부분에서 조금 손해 보고 뒤에서 더 버는 상황이 없다고 어떻게 장담하는가.

다른 하나는 누적합으로 돌아가는 길이다. 모든 부분배열의 합이 $P_j - P_i$ 꼴이므로, $P_j$ 를 훑으면서 지금까지 본 가장 작은 $P$ 를 빼면 답이 나온다. 이 방법도 $O(N)$ 이고, 사실 위의 갱신식과 같은 계산이다.

둘 다 추가 설명 — 왜 이어 붙이는 것이 최선인가에서 다룬다.

---

마치며

같은 문제를 세 번 풀었다. 후보는 세 번 모두 같았고 달라진 것은 후보를 보는 방법이다. $O(N^3)$ 은 후보마다 합을 처음부터 계산했다. $O(N^2)$ 은 합을 미리 만들어 뺄셈으로 바꿨다. $O(N)$ 은 후보를 나열하는 일 자체를 그만뒀다.

마지막 도약의 열쇠는 부분 문제를 ”$a_1 \dots a_i$ 의 뒷조각”으로 잡은 정의였다. 이 한 줄이 $\Theta(N^2)$ 개의 후보를 $N$ 개의 값으로 접었다. 문제를 어떻게 쪼개느냐가 알고리즘을 정한다.