추가 설명 — 왜 이어 붙이는 것이 최선인가

최대 부분배열은 자리마다 최선 하나만 들고 가면 된다고 했다. 이 글은 그 갱신에 손해가 없는 이유를 증명하고 누적합 관점의 다른 풀이와 이어 붙인다.

뜻은 본편 그대로 쓰고 인덱스만 정리한다. 배열은 $a_1, \dots, a_N$, 누적합은 $P_0 = 0$, $P_j = a_1 + \cdots + a_j$ 다. $k_j$ 는 $a_1 \dots a_j$ 의 뒷조각 중 최대 합이고, 뒷조각은 $a_1 \dots a_j$ 에서 앞의 몇 개를 잘라내고 남은 조각이다. 전부 잘라낸 빈 뒷조각도 후보에 넣는다.

글자를 하나 더 둔다. $j$ 는 지금 보고 있는 자리, $s$ 는 앞에서 잘라낸 자리로 끝까지 고정한다. 본편은 자리를 $i$ 로 적고 구간합을 $a_i + \cdots + a_j = P_j - P_{i-1}$ 로 적었는데, 이 글은 아래에서 두 관점을 한 식에 함께 놓아야 해서 글자를 갈라 둔다. 잘라낸 자리를 경계로 잡으면 뒷조각은 $a_{s+1} \dots a_j$ 이고 그 합은 $P_j - P_s$ 로 떨어져 $-1$ 이 붙지 않는다.

---

이어 붙이기가 최선인 이유

본편의 갱신식은 이렇다.

$$k_{j+1} = \max(k_j + x,\; 0), \qquad x = a_{j+1}$$

여기서 $k_j + x$ 를 ”$a_{j+1}$ 에서 끝나고 $x$ 를 포함하는 부분배열의 최대 합”이라고 주장했다. 의심할 만한 지점이 있다. 앞부분을 $k_j$ 를 내는 그 부분배열로 고정해 버리면, 시작점을 다르게 잡았을 때 뒤에서 더 벌 기회를 놓치는 것 아닌가.

놓치지 않는다. 두 후보 집합이 정확히 대응하기 때문이다.

증명. 세 단계로 나눠 본다. 후보를 짝짓고, 짝의 합을 비교하고, 최댓값을 옮긴다.

하나. 두 집합의 후보가 하나씩 짝을 이룬다. $T_{j+1}$ 의 후보는 모두 $x$ 로 끝난다. 그 $x$ 를 떼어 보자. 남는 것은 $a_1 \dots a_j$ 의 뒷조각, 곧 $S_j$ 의 후보다. $x$ 하나짜리였다면 아무것도 남지 않는데, 빈 뒷조각도 $S_j$ 의 후보이므로 이 경우도 빠지지 않는다. 거꾸로 $S_j$ 의 후보 아무거나 골라 뒤에 $x$ 를 붙이면 $T_{j+1}$ 의 후보가 된다. 떼기와 붙이기가 서로를 되돌리는 동작이라 짝이 빠지거나 겹치지 않는다.

둘. 짝지어진 두 후보의 합은 정확히 $x$ 만큼 차이 난다. 떼어낸 것이 $x$ 하나뿐이기 때문이다. $S_j$ 쪽 후보의 합이 $t$ 면 그 짝의 합은 $t + x$ 다.

셋. 그래서 최댓값도 짝을 이룬다. 모든 짝에 같은 $x$ 가 더해지므로 후보들의 순위가 뒤집히지 않는다. $S_j$ 에서 가장 큰 후보의 짝이 $T_{j+1}$ 에서도 가장 크다. $S_j$ 의 최대 합이 $k_j$ 이니 $T_{j+1}$ 의 최대 합은 $k_j + x$ 다.

같은 사실을 ”$k$ 배열의 시작점을 옮기면 반드시 $k$ 와 같거나 작은 값이 나온다”로 적을 수도 있다. 시작점을 옮긴 조각도 $S_j$ 의 후보이고, $k_j$ 는 $S_j$ 전체의 최댓값이니 그보다 클 수 없다. 손해를 뒤에서 만회할 수 없는 이유는, 뒤에 붙는 것이 어느 후보에게나 똑같이 $x$ 하나뿐이라서다.

숫자로 확인해 보자. $j = 5$, $x = a_6 = 3$ 이다. $S_5$ 의 원소를 합과 함께 적으면 빈 배열 0, $[a_5]$ 는 $-2$, $[a_4 a_5]$ 는 2, $[a_3 a_4 a_5]$ 는 4, $[a_2 \dots a_5]$ 는 $-1$, $[a_1 \dots a_5]$ 는 2다. 최댓값 4는 $k_5$ 와 맞는다. 각각에 3을 더하면 $3,\, 1,\, 5,\, 7,\, 2,\, 5$ 이고 최댓값은 7이다. $k_6 = \max(4 + 3,\, 0) = 7$ 과 맞는다. 순서가 하나도 바뀌지 않았다는 점이 이 논증의 전부다.

---

누적합으로 다시 보기

전혀 다른 길로 가도 $O(N)$ 이 나온다. 본편의 누적합을 다시 쓴다. 앞에서 잘라낸 자리를 $s$ 로 두면

$$a_{s+1} + a_{s+2} + \cdots + a_j = P_j - P_s$$

비어 있지 않은 부분배열 하나는 $0 \le s < j \le N$ 인 쌍 $(s, j)$ 와 1:1로 대응한다. 서로 다른 두 경계를 고르는 것이 곧 구간 하나를 고르는 것이다. $s = j$ 인 쌍도 식에 넣으면 값이 $P_j - P_j = 0$ 이 되는데, 어느 자리를 고르든 값이 0으로 같으므로 후보 $N+1$ 개가 아니라 빈 배열 하나를 더한 것과 다르지 않다. 따라서 답은

$$\max_{0 \le s \le j \le N} (P_j - P_s)$$

$j$ 를 고정하면 $P_j$ 는 상수이므로 $P_s$ 를 가장 작게 만들면 된다. 고를 수 있는 $s$ 는 $j$ 이하다.

$$\text{답} = \max_{0 \le j \le N} \left( P_j - \min_{0 \le s \le j} P_s \right)$$

이 최솟값을 앞으로 $m_j = \min_{0 \le s \le j} P_s$ 로 줄여 쓴다. $P$ 를 왼쪽에서 오른쪽으로 훑으면서 $m_j$ 를 들고 다니면 각 $j$ 의 항이 $O(1)$ 에 나온다. 이 방법이 정말 답을 내는지는 의심스러울 수 있는데, 위 두 줄이 그 근거다. 모든 부분배열이 $P_j - P_s$ 꼴이고 $j$ 마다 최선의 $s$ 를 고른 것뿐이라 빠뜨린 후보가 없다.

그림으로 보면 누적합 꺾은선에서 상승폭이 가장 큰 구간을 찾는 문제다. 왼쪽 어딘가의 골짜기에서 오른쪽 어딘가의 봉우리까지, 단 골짜기가 봉우리보다 왼쪽에 있어야 한다. 예시 배열에서는 $P_2 = -2$ 가 골짜기, $P_8 = 7$ 이 봉우리이고 상승폭은 9다.

$\min$ 의 범위가 $s < j$ 가 아니라 $s \le j$ 라는 점을 눈여겨볼 만하다. $s = j$ 를 허용하는 것이 곧 빈 배열을 허용하는 것이고, 그래서 이 식의 값은 항상 0 이상이다. 빈 배열을 허용하지 않으려면 $s < j$ 로 좁히면 된다. 그러면 $j$ 는 1부터 시작하고 최솟값은 $P_0, \dots, P_{j-1}$ 중에서 고른다.

---

두 풀이는 같다

두 방법이 우연히 같은 답을 내는 것이 아니다. 매 자리에서 같은 값을 계산한다.

왼쪽은 카데인이 자리마다 들고 다니는 값, 오른쪽은 누적합 풀이가 그 자리에서 만드는 값이다. 둘이 같다면 두 알고리즘은 같은 수열을 다른 방식으로 적어 내려가는 셈이다.

증명. $k_j$ 의 정의로 돌아가면 한 줄로 끝난다.

$k_j$ 는 $a_1 \dots a_j$ 의 뒷조각 중 최대 합이다. 뒷조각은 앞에서 $s$ 개를 잘라내고 남은 $a_{s+1} \dots a_j$ 이고, 앞 절에서 본 대로 그 합은 $P_j - P_s$ 다. 잘라내는 개수 $s$ 를 0부터 $j$ 까지 바꾸면 뒷조각이 하나씩 나온다. $s = j$ 는 전부 잘라낸 빈 뒷조각이고, 합도 $P_j - P_j = 0$ 으로 맞는다. 후보를 빠짐없이 적으면

$$k_j = \max_{0 \le s \le j} (P_j - P_s)$$

$P_j$ 는 어느 항에나 똑같이 들어 있는 상수다. 상수에서 무언가를 뺀 값을 크게 만들려면 빼는 쪽을 작게 만들면 되므로, $P_s$ 가 가장 작은 $s$ 를 고르는 것이 최선이다. 그 최솟값이 바로 $m_j$ 다.

$$k_j = P_j - \min_{0 \le s \le j} P_s = P_j - m_j$$

같은 후보 묶음을 두 번 센 것이다. 카데인은 뒷조각을 조각 그대로 보고, 누적합 풀이는 뒷조각을 두 경계의 차이로 본다. 세는 대상이 같으니 최댓값도 같다.

갱신식으로도 맞아떨어진다. 한 줄 증명이 미덥지 않다면 자리를 하나 넘길 때의 계산을 직접 맞춰 봐도 된다. $x = a_{j+1}$ 이라 하면 $P_{j+1} = P_j + x$ 이고, 새 최솟값은 $m_{j+1} = \min(m_j,\, P_{j+1})$ 이다. 둘 중 어느 쪽이 작으냐로 경우가 갈린다.

• 새 누적합이 최솟값을 못 깰 때 ($P_{j+1} > m_j$). 최솟값은 그대로라 $m_{j+1} = m_j$ 다. 차는 $P_{j+1} - m_j = (P_j - m_j) + x = k_j + x$ 이고, 가정에서 이 값은 0보다 크다.
• 새 누적합이 최솟값을 깰 때 ($P_{j+1} \le m_j$). 최솟값이 $m_{j+1} = P_{j+1}$ 로 갈아치워지고 차는 0이다. 이때 $k_j + x = P_{j+1} - m_j$ 는 0 이하이므로 0을 고르는 편이 맞다.

두 경우를 한 줄로 묶으면 $P_{j+1} - m_{j+1} = \max(k_j + x,\, 0)$, 본편의 갱신식 그대로다. 방금 쓴 $P_j - m_j = k_j$ 는 위에서 이미 증명한 등식이라 가정으로 끌어온 것이 아니다. 누적합 풀이가 최솟값을 갈아치우는 자리와 카데인이 구간을 끊고 새로 시작하는 자리가 정확히 겹친다는 것도 여기서 드러난다.

예시로 확인해 보자. $P_0 \dots P_8 = 0,\, 3,\, -2,\, 0,\, 4,\, 2,\, 5,\, -1,\, 7$ 이고 $m_0 \dots m_8 = 0,\, 0,\, -2,\, -2,\, -2,\, -2,\, -2,\, -2,\, -2$ 다. 차를 나열하면 $0,\, 3,\, 0,\, 2,\, 6,\, 4,\, 7,\, 1,\, 9$ 이고, 본편의 $k_0 \dots k_8$ 과 정확히 겹친다.

카데인은 $k_j$ 를 직접 굴린다. 누적합 풀이는 $P_j$ 와 $m_j$ 를 따로 들고 다니다 마지막에 뺀다. 들고 다니는 값의 개수만 다르고 계산하는 것은 같다.

---

훑기 세 번을 한 번으로

누적합 풀이를 식 그대로 옮기면 prefix sum, prefix minimum, 빼는 과정까지 배열을 세 번 훑는다. 세 번 훑어도 $O(N)$ 이라 복잡도는 같다. 한 번으로 합칠 수도 있다.

// 누적합 관점의 O(N).  배열을 한 번만 지나간다.
long long maxSubarrayPrefix(const vector<int>& a) {
    long long p = 0, m = 0, best = 0;   // p: 누적합, m: 지금까지의 최소 누적합
    for (int x : a) {
        p += x;
        best = max(best, p - m);        // 이 자리에서 끝나는 최선
        m = min(m, p);                  // 다음 자리를 위해 최솟값 갱신
    }
    return best;
}

m 을 갱신하기 전에 p - m 을 읽는 순서가 걱정될 수 있다. 이 자리에서 쓰는 최솟값은 $m_j$ 가 아니라 $m_{j-1}$ 이기 때문이다. 문제가 없는 이유는 best 가 항상 0 이상이라서다. $P_j - m_{j-1}$ 이 음수라면 $P_j$ 자신이 새 최솟값이 되어 $P_j - m_j = 0$ 인데, 0은 이미 best 에 반영되어 있다. 두 경우 모두 best 는 올바른 값을 유지한다.

본편의 카데인 코드와 나란히 놓으면 들고 다니는 상태가 다르다. 카데인은 자리에서 끝나는 최선 $k$ 하나를 갱신하고, 이 코드는 누적합 $p$ 와 최소 누적합 $m$ 을 따로 굴린다.

앞 절의 증명이 말해 주는 것은 두 풀이가 자리마다 같은 값 $P_j - m_j = k_j$ 를 정의한다는 사실이다. 두 코드가 그 값을 매번 계산한다는 뜻은 아니다. 방금 본 대로 이 구현은 $j$ 번째 반복에서 $P_j - m_{j-1}$ 을 읽는다. 예시의 $j = 2$ 에서 코드가 읽는 값은 $-2$ 이고 $k_2 = 0$ 이라 그 자리의 값 자체는 다르다. 일치하는 것은 best 가 유지하는 전체 최댓값이다.

---

마치며

본편이 넘긴 두 질문에 답했다. 갱신식이 옳은 이유는 후보 집합이 1:1로 대응하고 모든 후보에 같은 값이 더해져 순위가 보존되기 때문이다. 누적합에서 지금까지의 최소를 빼는 풀이가 옳은 이유는 모든 부분배열이 두 경계의 차이로 표현되기 때문이다.

두 답은 결국 한 식으로 모인다. $k_j = P_j - \min_{s \le j} P_s$. 자리마다 최선을 들고 가든 누적합의 상승폭을 재든 매 자리에서 같은 값이 나오므로, 둘 중 편한 쪽을 골라 쓰면 된다.

← 최대 부분배열