백준 1912 연속합 Java: Kadane 알고리즘과 음수 배열 처리

백준 1912번 ‘연속합’은 수열에서 하나 이상 연속된 값을 골라 합의 최댓값을 구한다. 현재 위치에서 끝나는 최댓값만 유지하면 한 번의 순회로 풀 수 있다. 이 점화식은 보통 Kadane 알고리즘이라고 부른다.

• 백준 1912번 연속합

이전 연속합에 붙일지 새로 시작할지 결정한다

현재 값이 value이고 이전 index에서 끝나는 최대 연속합이 current라면 선택지는 두 개다.

이전 구간에 현재 값을 붙인다: current + value
현재 값부터 새 구간을 시작한다: value

따라서 상태는 다음 한 줄로 갱신된다.

current = max(value, current + value)
best = max(best, current)

이전까지의 합이 음수라면 현재 값에 붙이는 순간 오히려 작아지므로 버리고 새로 시작한다. 반대로 양수라면 붙이는 것이 현재 값 하나보다 항상 크다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int count = Integer.parseInt(reader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int current = Integer.parseInt(tokenizer.nextToken());
        int best = current;

        for (int index = 1; index < count; index++) {
            int value = Integer.parseInt(tokenizer.nextToken());
            current = Math.max(value, current + value);
            best = Math.max(best, current);
        }

        System.out.println(best);
    }
}

모든 값이 음수인 경우

current와 best를 0으로 시작하면 빈 구간을 선택한 것처럼 0이 답이 된다. 문제는 하나 이상의 수를 선택해야 하므로 첫 번째 값으로 초기화한다.

-5 -2 -8

이 수열의 답은 0이 아니라 -2다. current = max(value, current + value)는 각 위치에서 음수 중 덜 작은 값을 새 시작점으로 선택한다.

원문의 0 reset과 같은 생각

원문에서는 값을 더하다 누적합이 0보다 작아지면 0으로 reset하고, 전체 최댓값은 따로 보존했다. all-negative 입력을 위해 각 원소 자체도 best와 비교했다. 결과적으로 같은 원리를 조금 더 많은 상태로 표현한 것이다.

max(value, current + value)로 쓰면 “reset할까?”와 “현재 음수를 답 후보로 볼까?”가 한 식에 포함된다. 연속 구간의 시작·끝 index까지 필요하다면 새로 시작하는 branch에서 start index를 갱신하고 best가 바뀔 때 두 index를 보존하면 된다.

시간 복잡도는 O(N), 배열을 저장하지 않으므로 추가 공간은 O(1)이다. 고정 길이 K의 연속합은 백준 2559 수열처럼 prefix sum이나 sliding window가 더 직접적이다.

어렵다고 미리 단정했던 기록

원문에는 손으로 수열을 적다가 어느 순간 규칙을 깨닫고 나서는 술술 풀렸다고 적혀 있다. 단계별 DP 뒤쪽에 있는 문제라는 이유로 스스로 어려울 것이라고 되뇌면서 오히려 오래 걸렸다는 성찰도 남겼다.

DP에서 상태를 거창하게 잡기 전에 “현재 index에서 반드시 끝나는 답”을 한 문장으로 제한하면 2차원 table 없이도 점화식이 보일 때가 있다. 이 글에서 남길 학습은 문제가 쉽다는 평가보다 그 상태 축소 과정이다.

검증 범위

Java source를 수동 검토하고 원소 1개, all-negative, all-positive, 여러 번 restart되는 수열과 작은 random sequence를 모든 연속 구간 brute force와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.