[알고리즘] 백준 1912 연속합

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

1912번: 연속합

import java.util.Scanner;

public class BJ_1812 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        int[] dp = new int[n];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
            max = Integer.max(max, arr[i]);
        }

        dp[0] = arr[0];

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

        System.out.println(max);
    }
}

DP 문제이다.

 

연속적인 수들의 합이므로 dp기법으로 맨 왼쪽부터 하나씩 더해나간다.

 

이때 분기가 세가지로 나뉘는데

 

1. 이전 인덱스 + 현재 인덱스가 가장 큰 경우

 

2. 이전 인덱스 + 현재 인덱스값보다 현재 인덱스가 큰 경우(이때는 이전 dp값들, 즉 왼쪽부터 더해나가던 값을 버림)

 

3. 예전값이 가장 큰 경우 (dp값보다 이전에 저장된 값이 더 큰 경우)

 

로 나누어 max값을 출력한다.