[백준]1912번 연속합(java)

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

1912번: 연속합

백준 1912번 연속합 문제 링크입니다.

핵심

연속된 수의 합이 가장 큰 값을 찾는 것이다. 이전까지 탐색했던 값과 새로운 값을 비교해나가면 쉽게 풀 수 있다.

정답 코드

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        int[] dp = new int[N];
        for(int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        dp[0] = arr[0];
        int max = arr[0];
        for (int i = 1; i < N; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

해설

dp [0] 이전에 탐색할 부분이 없기 때문에 arr [0]으로 초기화한다.

이전까지의 합을 구하면서, 새로운 값과 비교하여 더 큰 값을 ap [i]에 넣는다.

그 순간마다 최댓값을 저장한다.

 

 

개선점이나 오류가 있다면 댓글 부탁드립니다.