연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1

끝나는 위치를 고정한 점화식

전체 부분 배열을 모두 열거하면 시작과 끝의 조합이 O(N²)개다. 대신 D[i]를 i번째 수를 반드시 포함하고 i에서 끝나는 연속 구간의 최대 합으로 둔다. 이전의 최선 구간에 현재 수를 이어 붙이거나, 이전 구간을 버리고 현재 수부터 새로 시작하는 두 선택만 있다. 그래서 D[i]=max(D[i−1]+a[i], a[i])가 된다. 전체 정답은 모든 D[i]의 최댓값이다.

첫 예제에서 앞쪽 10,-4,3,1,5,6의 합은 21이다. 여기에 −35를 붙이면 −14가 되므로 이 위치의 최선은 −14로 떨어진다. 다음 12에서는 −14+12보다 12부터 다시 시작하는 편이 낫고, 이어 21을 더해 33이 된다. 이전 합이 음수면 그 구간을 끌고 갈 이유가 없다는 직관이 점화식에 들어 있다.

모든 값이 음수일 때 정답을 0으로 초기화하면 빈 구간을 고른 셈이 되어 틀린다. 코드가 첫 원소로 dp[0]과 result를 시작하는 이유다. N=1도 그대로 처리한다. 현재 코드는 O(N) 시간과 O(N) 배열 공간을 쓰지만, 직전 D값 하나만 유지하면 추가 공간을 O(1)로 줄일 수 있다.

읽은 값	그 위치에서 끝나는 최대 합 D[i]	전체 최대
6	21	21
−35	−14	21
12	12	21
21	33	33
−1	32	33

전체 최댓값과 “현재 위치에서 끝나는 합”은 다르다. −35를 만났을 때 전체 최댓값 21을 잃어버리면 안 되고, 12를 만났을 때 이전 구간 −14를 억지로 이어 붙여서도 안 된다. 코드가 dp[i]와 result를 따로 유지하는 이유다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        
        String[] split = in.readLine().split(" ");
        int[] a = new int[t];
        for (int i = 0; i < split.length; i++) {
            a[i] = Integer.parseInt(split[i]);
        }
        out.write("" + continuitySum(a));
        out.flush();
        in.close();
        out.close();
    }

    public static long continuitySum(int[] a) {
        long[] dp = new long[a.length];
        long result = dp[0] = a[0];
        for (int i = 1; i < a.length; i++) {
            dp[i] = Math.max(dp[i-1] + a[i], a[i]);
            if (result < dp[i]) {
                result = dp[i];
            }
        }
        return result;
    }
}

백준 원문 문제