[백준] 13398번 : 연속합 2 - JAVA [자바]

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

두 가지의 상황이 있다.
1. 수를 제거 안했을 때의 연속합의 최대
2. 수를 제거 했을 때의 연속합의 최대

0 : 수를 제거했을 때
1 : 수를 제거 안했을 때

그러면 int[][] dp = new int[N + 1][2] 로 배열을 정의할 수 있다.

dp[i][0] : 수를 제거 안할때의 연속합의 최대
Math.max(dp[i-1][0] + arr[i], arr[i])이다.
즉, i 번째 수를 전의 수와 연속해서 더했을 때와 i 번째 수를 처음으로했을 때를 비교해서 큰 것을 선택한다.

dp[i][1] 는 두 가지 상황이 있다.

1. i 번째 수가 처음으로 제거되는 경우: dp[i-1][0] (그전까지의 제거안했을 때의 연속합)
2. i 번째 수 전에 제거된 수가 있는 경우: dp[i-1][1] + arr[i] (그 전에 제거된 연속합 + i 번째 수)

두 가지를 비교해서 더 큰 것을 선택한다.

public class bj13398 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        // 두가지 경우가 있다
        // dp[i][0] : 특정 수를 제거하지 않을 때
        // Math.max(dp[i - 1][0] + arr[i], arr[i])
        // dp[i][1]
        // 1. i 번째 수가 처음으로 제거되는 경우: dp[i-1][0]
        // 2. i 번째 수 전에 제거된 수가 있는 경우: dp[i-1][1] + arr[i]
        int[][] dp = new int[N + 1][2];

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

        for (int i = 2; i < N + 1; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + arr[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]));
        }


        bw.write(max + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}