[백준](Java) 1912 - 연속 합

문제 링크

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

문제 풀이

DP문제는 점화식을 만들수 있게 되면 간단한데 그전까지는 어려운것 같다.
이전까지의 최댓값들의 연속된 합을 dp에 담는다.
dp[0]은 arr[0]의 값을 가지며, dp[1]은 arr[1]과 dp[0]+arr[1]값을 비교해서 더 큰값을 가지게 된다. dp[0]이 음수인경우에는 arr[1]이 클것이며, arr[1]이 음수일 경우에는 dp[0]+arr[1]이 더 클것이다.

이와 같은 방법을 점화식으로 세우면

dp[i] = Math.max(arr[i], dp[i - 1] +arr[i]);

와 같이 나오게 되며 연산이 이루어질때마다 최대값을 answer에다가 저장해둔다.

코드

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long answer = 0;
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        long[] dp = new long[n];
        dp[0] = arr[0];
        answer = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(arr[i], dp[i - 1] +arr[i]);
            answer = Math.max(answer,dp[i]);
        }
        System.out.println(answer);
    }
}