1912번: 연속합

문제

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

• 입력: 첫째 줄에 정수 n (1 ≤ n ≤ 100,000)이 주어지고, 둘째 줄에 n개의 정수로 이루어진 수열이 주어집니다.
• 출력: 첫째 줄에 가장 큰 연속합을 출력합니다.

링크: https://www.acmicpc.net/problem/1912

풀이: 다이나믹 프로그래밍 (DP)

이 문제는 이전까지의 계산 결과를 활용하여 현재의 최적해를 구하는 전형적인 다이나믹 프로그래밍(DP) 문제입니다. (카데인 알고리즘과 동일한 원리입니다.)

1. DP 배열 정의: d[i]를 i번째 원소를 마지막으로 포함하는 연속 부분 수열의 최대 합이라고 정의합니다.
2. 점화식 도출: i번째 원소에서 선택할 수 있는 경우는 두 가지입니다.
   • 이전까지의 연속합에 현재 숫자를 이어 붙이는 경우: d[i - 1] + a[i]
   • 이전까지의 연속합을 끊고, 현재 숫자부터 새롭게 연속합을 시작하는 경우: a[i]
   즉, 둘 중 더 큰 값을 선택하여 d[i]에 저장합니다. 작성하신 코드와 같이 d[i] = a[i]로 둔 뒤, d[i] = Math.max(d[i - 1] + a[i], d[i]) 형태로 갱신할 수 있습니다.
3. 최댓값 갱신: 수열 내에 음수가 모두 포함되어 있을 수 있으므로, 연속합의 최댓값을 저장할 변수 ans의 초기값은 Integer.MIN_VALUE로 설정해야 합니다. d 배열을 채워나가면서 매번 ans를 갱신해 주면, 최종적으로 전체 수열에서의 가장 큰 연속합을 얻을 수 있습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       
       int[] a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       int[] d = new int[n];
       Arrays.fill(d, Integer.MIN_VALUE);
       int ans = Integer.MIN_VALUE;
       
       for (int i = 0; i < n; i++) {
          d[i] = a[i];
          if (i > 0) {
             d[i] = Math.max(d[i - 1] + a[i], d[i]);
          }

          ans = Math.max(ans, d[i]);
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

다이나믹 프로그래밍 (DP)