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

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

13398번: 연속합 2

 

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[] arr = new int[n];
        int[][] dp = new int[n][2];

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

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

        for(int i=1; i<n; i++){
            // 1. 특정 수를 제거하지 않을 때
            dp[i][0] = Math.max(dp[i-1][0]+arr[i], arr[i]);
            // 2. 특정 수를 제거 할 때
            // 2-1) i번째 수가 처음 제거 되는 경우: 이전 최대 연속합을 할당
            // 2-2) i번째 수 전에 제거된 수가 있는 경우: 이전 최대 연속합 + arr[i]
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]+arr[i]);

            answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
        }
        System.out.println(answer);
    }
}

 

https://yeoncoding.tistory.com/602

[JAVA] 백준 1912번 - 연속합

 

 

특정 수를 제거 할때와 제거하지 않을 때를 나누기 위하여 dp를 이차원배열로 표현한다.

 

 

1. j=0 (수를 제거하지 않을 때)

 

이전 연속합 문제와 동일하게 dp[i-1][0] + arr[i] 과 arr[i] 중 큰 값을 고른다. 

 

 

2. j=1 (특정 수를 제거할 때)

 

2-1. 특정 수를 처음 제거할 때

dp[i][1] = dp[i-1][0]

 

2-2. 특정 수 전에 제거된 수가 있을 때

dp[i][1] = dp[i-1][1] + arr[i]

 

특정 수를 처음 제거할 경우에는 두가지 경우로 나누어 비교한다.

특정수를 처음 제거할 때는 dp[i][1]에 수를 제거하지 않은 경우의 최대 연속합을 할당한다.

특정 수 전에 이미 제거된 수가 있을 때에는 수를 제거했을 경우의 이전 최대 연속합에 arr[i]를 더한다.

이 두가지 경우 중 큰 값을 고른다.