Baekjoon 1912 연속합 JAVA

해당 문제는 DP를 이용하여 간단하게 해결하였다.

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

1912번: 연속합

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201912

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 N 개의 정수로 이루어진 임의의 수열이 주어지면 이 수열 중에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제다.

조건

수는 한 개 이상 선택해야 한다.

​

해당 문제는 DP를 이용해서 처음 arr 배열에 임의의 수열을 입력받으면 arr[0]=dp[0] 을해주고 이후 1부터 N까지 반복문을 돌리면서 arr[i]와 arr[i]+dp[i-1] 중에서 최댓값을 dp에 넣으면서 값을 비교해나가면 된다. 이후 dp 배열을 정렬해 주고 가장 마지막 값을 출력해 주면 해결 가능한 문제다.