[13398] 연속합 2

✔ 연속합 2

[백준 13398]

문제 분석하기

0에서 N까지 길이에서 N을 포함하며 연속으로 수를 선택하여 구할 수 있는 최대 합을 동적 계획법으로 구하도록 함

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[N]은 0에서 N까지 길이에서 N을 포함하며 연속으로 수를 선택하여 구할 수 있는 최대 합
2. 점화식을 구함
   • 이때 1개의 수를 삭제할 수 있기 때문에 왼쪽 방향에서부터 인덱스를 포함하여 최대 연속 합을 구하고,
     오른쪽 방향에서부터 인덱스를 포함하여 최대 연속 합을 한 번 더 구한 후
     L[N - 1] + R[N + 1]을 하여 N을 1개 제거한 최댓값을 구하는 효과를 얻도록 함 
   • L[N] : 왼쪽에서부터 N을 포함한 최대 연속 합을 나타내므로
     L[i] = Math.max(A[i], L[i - 1] + A[i])
   • R[N] : 오른쪽에서부터 N을 포함한 최대 연속 합을 나타내므로
     R[i] = Math.max(A[i], R[i + 1] + A[i])
3. 점화식으로 배열을 채운 후 계산된 두 배열을 이용해 최댓값을 찾도록 함
   

슈도코드 작성하기

N(배열 크기) A(수열 데이터 저장하기 배열)
L(왼쪽에서 오른쪽 방향으로 index를 포함한 최대 연속 합을 나타내는 배열)
R(오른쪽에서 왼쪽 방향으로 index를 포함한 최대 연속 합을 나타내는 배열)
for(i -> 0 ~ N) {
    A 배열 저장하기
}
for(i -> 1 ~ N) {
    L[i] = Math.max(A[i], L[i - 1] + A[i])
    L 배열의 최댓값을 정답 변수에 저장하기
}
for(i -> N - 2 ~ 0) {
    R[i] = Math.max(A[i], R[i + 1] + A[i])
}
for(i -> 1 ~ N - 1) {
    기존 정답 변수에 L[i - 1] + R[i + 1]로 계산한 값 중 최댓값
}
최댓값 출력하기

코드 구현하기

/**
 * 13398) 연속합2
 */
public class D089_13398 {
    static int N;
    static int[] A;
    static int[] L;
    static int[] R;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(배열 크기)
        N = Integer.parseInt(br.readLine());
        // A(수열 데이터 저장하기 배열)
        A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        // A 배열 저장하기
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        // L(왼쪽에서 오른쪽 방향으로 index를 포함한 최대 연속 합을 나타내는 배열)
        L = new int[N];
        L[0] = A[0];
        result = L[0];
        // 오른쪽 방향으로 index를 포함한 최대 연속 합 구하기
        for (int i = 1; i < N; i++) {
            L[i] = Math.max(A[i], L[i - 1] + A[i]);
            // L 배열의 최댓값을 정답 변수에 저장하기
            result = Math.max(result, L[i]); // 1개도 삭제하지 않았을 때 최댓값
        }
        // R(오른쪽에서 왼쪽 방향으로 index를 포함한 최대 연속 합을 나타내는 배열)
        R = new int[N];
        R[N - 1] = A[N - 1];
        // 왼쪽 방향으로 index를 포함한 최대 연속 합 구하기
        for (int i = N - 2; i >= 0; i--) {
            R[i] = Math.max(A[i], R[i + 1] + A[i]);
        }
        // L[i - 1] + R[i + 1] 2개의 구간 합 배열을 더하면 i번쩨 값을 제거한 효과
        for (int i = 1; i < N - 1; i++) {
            // 기존 정답 변수에 L[i - 1] + R[i + 1]로 계산한 값 중 최댓값
            int temp = L[i - 1] + R[i + 1];
            // 삭제하지 않았을 때와 삭제했을 때의 최댓값 비교
            result = Math.max(result, temp);
        }
        // 최댓값 출력하기
        System.out.println(result);
    }
}