[백준 1912] 연속합 (Java)

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

1912번: 연속합

접근 방법

다이나믹 프로그래밍 문제였다.

입력받은 수열은 numbers 배열에 담고

dp라는 배열을 하나 더 만들었다.

 

dp에는 i번째까지의 연속합 중 최댓값을 담았다.

i번째까지의 연속합 중 최댓값은 이전까지 연속합 중 최댓값(dp[i-1])에 i번째의 수를 더한 값(numbers[i])과 i번째 수를 비교해 큰 값이 해당한다. 이전까지의 합에 현재 수를 더한 것보다 현재 수가 더 크다면 다시 새로 시작해야하는 것이다.

 

점화식은 다음과 같다.

dp[n] = Max(dp[n-1] + numbers[i], numbers[i])

 

최종적으로 dp배열 원소 값 중 최대값을 출력하면 된다.

 

소스 코드

import java.util.Scanner;

public class Main {

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

        int n = scanner.nextInt();
        int[] numbers = new int[n + 1];
        int[] dp = new int[n + 1];

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

        dp[1] = numbers[1];
        int max = dp[1];

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

        System.out.println(max);
    }
}