[Java] 백준 13398번: 연속합 2

[문제 바로 가기] - 연속합 2

📌 유형 : dp

💡 아이디어

주어진 N개의 정수 중 연속된 수를 선택했을 때 가장 큰 합을 구하는 문제로 특이한 점은 하나의 수를 제거하고 선택할 수 있다는 것이다.

10
10 -4 3 1 5 6 -35 12 21 -1

예제에서 수를 제거하지 않았을 땐 최댓값은 12+21 = 33이 되지만, -35를 제거하면 최댓값은 10-4+3+1+5+6+12+21 = 54가 된다.

처음엔 왼쪽에서 오른쪽 방향으로의 누적합을 구한 뒤 음수인 값을 빼주어야 하나 생각했는데 풀이가 생각나지 않아 dp 풀이를 찾아봤다.

먼저 dp1에는 왼쪽에서 오른쪽으로의 누적합을 저장하고 dp2에는 오른쪽에서 왼쪽으로의 누적합을 저장한다. (dp1[0] = nums[0], dp[N - 1] = nums[N - 1]로 초기화)

이때 연속합의 최댓값이 될 answer는 dp1[0]으로 초기화해주어야 한다.

1
-1

왜냐하면 처음에 answer를 Integer.MIN_VALUE로 선언했더니 이 예제에서 걸렸다.

	// 왼 -> 오 누적합
	for (int i = 1; i < N; i++) {
		dp1[i] = Math.max(nums[i] + dp1[i - 1], nums[i]);
		answer = Math.max(answer, dp1[i]);
	}
		
	// 오 -> 왼 누적합
	for (int i = N - 2; i >= 0; i--) {
		dp2[i] = Math.max(nums[i] + dp2[i + 1], nums[i]);
		answer = Math.max(answer, dp2[i]);
	}

이 과정에서 answer를 지속적으로 dp1[i]과 dp2[i]를 비교해가며 갱신한다.

이후 i번째 값을 제거한다고 가정하고 dp1[i - 1]과 dp2[i + 1]의 값을 answer와 비교하면 최종 answer가 나온다.

	// i번째를 제외한 합
	for (int i = 1; i < N - 1; i++) {
		answer = Math.max(answer, dp1[i - 1] + dp2[i + 1]);
	}

---

풀이

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[] nums = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp1 = new int[N]; // 왼쪽에서 오른쪽 방향으로
		int[] dp2 = new int[N]; // 오른쪽에서 왼쪽 방향으로
		
		dp1[0] = nums[0];
		int answer = dp1[0];
		
		// 왼 -> 오 누적합
		for (int i = 1; i < N; i++) {
			dp1[i] = Math.max(nums[i] + dp1[i - 1], nums[i]);
			answer = Math.max(answer, dp1[i]);
		}
		
		// 오 -> 왼 누적합
		dp2[N - 1] = nums[N - 1];
		for (int i = N - 2; i >= 0; i--) {
			dp2[i] = Math.max(nums[i] + dp2[i + 1], nums[i]);
			answer = Math.max(answer, dp2[i]);
		}
		
		// i번째를 제외한 합
		for (int i = 1; i < N - 1; i++) {
			answer = Math.max(answer, dp1[i - 1] + dp2[i + 1]);
		}
		
		System.out.println(answer);
	}
}