[백준] 13398번 연속합2

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

13398번: 연속합 2

 

• 숫자를 제거하지 않은 경우 : 0
•  숫자를 제거한 경우 : 1로 나누어서 생각

특정 숫자를 제거했을 때

1. i번째 수가 처음 제거 : 이전 최대 연속 합 할당

2. i번째 수 이전 제거된 수 있음 : 현재 수는 지울 수 없으므로 이전 최대 연속합에 arr[i] 를 더함

 

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());

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

        for(int i = 1; i <= n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }

        // 0일 때 특정 수 제거하지 않음
        // 1일 때 특정 수 제거
        dp[1][0] = arr[1];
        dp[1][1] = arr[1];

        int max = arr[1];

        for(int i =2; i <= n; i++) {
            dp[i][0] = Math.max(dp[i-1][0] + arr[i], arr[i]);

            // 특정 수 제거
            // 1. i번째 수가 처음 제거 : 이전 최대 연속 합 할당
            // 2. i번째 수 이전 제거된 수 있음 : 현재 수는 지울 수 없으므로 이전 최대 연속합에 arr[i] 를 더함
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + arr[i]);

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

        }

        System.out.println(max);
    }

}