[백준](Java) 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);
}
}
Author And Source
이 문제에 관하여([백준](Java) 1912 - 연속 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@courage331/백준Java-1912-연속-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)