백준 27210번: 신을 모시는 사당

문제 설명

• https://www.acmicpc.net/problem/27210
• 구간합이 최대가 되는 값을 구하는 문제입니다.

접근법

• 핵심은 연속된 값이 음수가 되면 해당 구간은 버리는 것입니다. 예를 들어 살펴보겠습니다.
  • [왼,왼,오,왼,왼,왼]: 첫번째와 두번째 왼쪽을 포함해야 가장 긴 4를 구할 수 있습니다.
  • [왼,왼,오,오,오,왼,왼,왼,왼]: 첫번째와 두번째 왼쪽을 포기해야 가장 긴 4를 구할 수 있습니다.
    처음 [왼,왼]이 이후 나오는 왼으로 구성된 어떤 긴 집합에 합류하려면 반드시 [오,오,오]를 포함해야 합니다. 하지만 [왼,왼,오,오,오]는 오른쪽이 더 많아 왼으로 구성된 어떤 긴 집합에는 오히려 손해가 됩니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		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++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = (num == 2)?-1:1;
		}
		
        // 풀이 1
		int[][] dp = new int[2][N+1];
		int answer = 0;
		for (int i = 1; i <= N; i++) {
			int num = arr[i-1];
			if(num == 1) {
				dp[0][i] = dp[0][i-1] + 1;
				dp[1][i] = Math.max(0, dp[1][i-1]-1);
			}else {
				dp[0][i] = Math.max(0, dp[0][i-1]-1);
				dp[1][i] = dp[1][i-1] + 1;
			}
			answer = Math.max(Math.max(dp[0][i], dp[1][i]),answer);
		}        
        
        // 풀이 2
		int sum = 0;
		int answer = 0;
		for (int i = 0; i < N; i++) {
			sum = (sum + arr[i] < 0)?0:sum + arr[i];
			answer = Math.max(answer, sum);
		}
		sum = 0;
		for (int i = 0; i < N; i++) {
			sum = (sum - arr[i] < 0)?0:sum - arr[i];
			answer = Math.max(answer, sum);
		}
        
		System.out.println(answer);		
	}
}