[JAVA] 백준 13398 DP

 

 

 

13398번: 연속합 2

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

풀이

이 문제의 키 포인트는 자신을 포함한 n개의 수열에서의 최댓값을 구하는 배열을 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 구한다.

이때, left[i-1] + right[i+1]은 i번째의 수를 뺀 값이라는 것이다.

📌 좌측 수열의 합의 최댓값 배열

        int max = -1001;
        int[] left = new int[N];
        max = Math.max(max, left[0] = A[0]);
        for(int i=1; i<N; i++){
            left[i] = Math.max(left[i-1]+A[i], A[i]);
            max = Math.max(left[i], max);
        }

• 이어지는 수열에서 이전의 최댓값과 자신을 더한 값, left[i-1] + A[i]과 자신 A[i] 중에서 더 큰 값을 현재 배열에 추가해준다.
• 각각의 이어지는 수열이 최댓값일 수 있기 때문에 max값도 갱신해준다.

📌 우측 수열의 합의 최댓값 배열

        int[] right = new int[N];
        right[N-1] = A[N-1];
        for(int i=N-2; i>=0; i--){
            right[i] = Math.max(right[i+1]+A[i], A[i]);
        }

• 우측도 마찬가지로 오른쪽에서 왼쪽으로 발견된 최댓값 + 자신과 자신 중에 더 큰 값을 선택해준다.

📌 수열에서 하나를 뺀 값의 최댓값

        for(int i=1; i<N-1; i++){
            int value = Math.max(max, left[i-1] + right[i+1]);
            max = Math.max(value, max);
        }

• i번째 수열의 값을 빼주고 최댓값을 계속 갱신해준다.

📌 전체 코드

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

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[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        int max = -1001;
        int[] left = new int[N];
        max = Math.max(max, left[0] = A[0]);
        for(int i=1; i<N; i++){
            left[i] = Math.max(left[i-1]+A[i], A[i]);
            max = Math.max(left[i], max);
        }

        int[] right = new int[N];
        right[N-1] = A[N-1];
        for(int i=N-2; i>=0; i--){
            right[i] = Math.max(right[i+1]+A[i], A[i]);
        }

        for(int i=1; i<N-1; i++){
            int value = Math.max(max, left[i-1] + right[i+1]);
            max = Math.max(value, max);
        }
        System.out.println(Math.max(max, right[N-1]));

    }

}

결과