[백준저지] 13398번 : 연속합 2

www.acmicpc.net/problem/13398

1. 문제

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

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

 

입)

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출)

첫째 줄에 답을 출력한다.

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] D1 = new int[N];
        int[] D2 = new int[N];
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        // i 부터 시작하는 최대 연속합
        for (int i = 0; i < N; i++) {
            D1[i] = A[i];
            if (i == 0) {
                continue;
            }
            if (D1[i-1] + A[i] > A[i]) {
                D1[i] = D1[i-1] + A[i];
            }
        }
        // N-1부터 시작하는 최대 연속합
        for (int i = N-1; i >= 0; i--) {
            D2[i] = A[i];
            if (i == N-1) {
                continue;
            }
            if (D2[i+1] + A[i] > A[i]) {
                D2[i] = D2[i+1] + A[i];
            }
        }
        // A[i]를 제거 안했을 때 최대값
        // D1[i]의 max값
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            if (D1[i] > result) {
                result = D1[i];
            }
        }
        // A[i]를 제거했을 때 최대값과 비교
        for (int i = 1; i < N-1; i++) {
            if (D1[i-1] + D2[i+1] > result) {
                result = D1[i-1] + D2[i+1];
            }
        }
        System.out.println(result);
    }
}

i번째 값을 뺀 것도 계산하기 위해서 D1, D2로 양쪽으로 각각 계산.

D1[i] => i번째 수에서 끝나는 최대 연속합

D2[i] => i번째 수에서 시작하는 최대 연속합

i번째 수를 안빼고 처음부터 쭉 최대 연속합 구한 값과 i번째 수를 빼고 앞에서 연속합과 뒤에서 연속합의 값과 비교

max(D1[i], D1[i-1] + D2[i+1]) 이 정답.