[백준] 1912. 연속합 (자바 JAVA)
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1
10
10 -4 3 1 5 6 -35 12 21 -1
예제 출력 1
33
예제 입력 2
10
2 1 -4 3 4 -4 6 5 -5 1예제 출력 2
14예제 입력 3
5
-1 -2 -3 -4 -5예제 출력 3
-1
접근 방법 🧐
시간 제한이 1초라서 최대 1억개의 루프 안에 해결해야 하기 때문에
이중 for문으로 max값을 갱신시키는 방법으로 접근하면 시간초과가 발생할 것이다.
입력 크기가 200,000이기 때문에 O(n^2)을 하면 40,000,000,000, 즉 4백억이라는 시간이 걸린다.
그래서 이 문제는 동적계획법(dp)로 해결해야 한다.
우선 연속된 값들의 합을 구하는 방법은 크게 2가지이다.
1. 이전까지 연속적인 합에 현재 숫자를 더하는 방법
2. 이전까지의 연속적인 합을 버리고 현재 숫자만 택하는 방법
예를 들어 3 -7 16이라는 수열이 있다고 생각하자.
여기서 3번째 시점에서의 연속 합을 구하려면
1) 16만 선택하거나
2) 이전 수열의 합인 -4에 16을 더한 12를 선택한다.
이 2가지이다.
여기서 이전 수열의 최대 합은 dp[i-1]로 표현할 수 있고,
연속합을 저장하는 것을 점화식으로 표현하면 다음과 같다.
dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
내가 쓴 코드 ✍️
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[n];
int max = arr[0];
dp[0] = arr[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
}