[백준] 13398. 연속합 2 (Java)

문제

13398번: 연속합 2

 

 

알고리즘

다이나믹 프로그래밍 (DP)

 

 

풀이

[2][n+1] 크기의 2차원 배열 dp를 선언하고 다음과 같이 값을 저장한다.

dp[0][i] = 값을 제거한 적 없는 i번째 수까지의 최대 연속합

dp[1][i] = 값을 제거한 적 있는 i번째 수까지의 최대 연속합

 

i 번째 수를 num이라고 할 때,

dp[0][i] 는 dp[0][i-1] 가 0보다 작다면 이전까지의 연속합을 버리고, num 부터 새로 시작하는 것이 더 큰 값을 만들 수 있다.

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

 

dp[1][i] 는 dp[1][i-1] + num 보다 dp[0][i-1] 가 더 클 경우 이번 num을 제거하는 것으로 더 큰 값을 만들 수 있다.

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

 

따라서 수열을 끝까지 탐색하며 dp[0][i], dp[1][i] 값 중 최댓값을 갱신하여 출력한다.

 

 

* 문제에서 최대 1개의 수를 선택해야한다는 조건이 있기 때문에 dp[0][1] 을 arr[1]로, max 또한 arr[1]로 초기화해야한다.

dp[0][1] 을 초기화 하지않으면 음수로만 이루어진 경우 0 을 답으로 출력하고,

max 값을 Integer.MIN_VALUE 등 다른 값으로 초기화해두면 수열 크기가 1인 경우 MIN_VALUE를 그대로 출력한다.

 

 

코드

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[][] dp = new int[2][n + 1];
		int[] arr = new int[n + 1];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= n; i++)
			arr[i] = Integer.parseInt(st.nextToken());

		int max = arr[1];
		dp[0][1] = arr[1];

		for (int i = 2; i <= n; i++) {
			int num = arr[i];

			dp[0][i] = Math.max(dp[0][i - 1] + num, num);
			dp[1][i] = Math.max(dp[1][i - 1] + num, dp[0][i - 1]);
			max = Math.max(max, Math.max(dp[0][i], dp[1][i]));
		}

		System.out.println(max);
	}
}