BOJ01912 연속합

https://www.acmicpc.net/problem/1912 (opens new window)

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

다이나믹 프로그래밍

dp[i] == array[i] (i == 0)
dp[i] == max(dp[i - 1] + array[i], array[i]) (i > 0)

dp[i - 1]은 이전까지 연속적으로 가지고 있는 합 중 가장 큰 값을 저장하기 위한 dp 테이블이다. 위 공식을 적용하면 아래 표와 같이 표현이 가능하다.

index	0	1	2	3	4	5	6	7	8	9
array	10	-4	3	1	5	6	-35	12	21	-1
dp	10	6	9	10	15	21	-14	12	33	32

제출 코드

다이나믹 프로그래밍 bottom-up 방식을 활용하여 풀이하였다.

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1912 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] array = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        dp[0] = array[0];
        int max = array[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}

#BOJ #다이나믹 프로그래밍