백준 13398 - 연속합 2(Java)

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

13398번: 연속합 2

코드 :

dp - bottom up

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] nums;
    static int[] dp1; //정방향
    static int[] dp2; //역방향

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        nums = new int[n + 1];
        dp1 = new int[n + 1];
        dp2 = new int[n + 1];

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


        dp1[1] = nums[1];
        dp2[n] = nums[n];

        //이 부분을 안넣어서 계속 틀렸다.
        int answer = dp1[1];

        //왼 -> 오 방향 연속합 저장, 기본적인 연속합의 최댓값도 저장
        for (int i = 2; i <= n; i++) {
            dp1[i] = Math.max(dp1[i - 1] + nums[i], nums[i]);

            answer = Math.max(answer, dp1[i]);
        }

        //오 -> 왼 방향 연속합 저장
        for (int i = n-1; i >= 1; i--) {
            dp2[i] = Math.max(dp2[i + 1] + nums[i], nums[i]);
        }

        //특정 값 제거한 경우 연속합 최댓값
        for (int i = 2; i < n; i++) {
            int temp = dp1[i - 1] + dp2[i + 1];
            answer = Math.max(answer, temp);
        }

        System.out.println(answer);
    }
}

풀이 :

연속합 구하는 문제를 응용하는 문제다. 

https://programming-beard.tistory.com/135

백준 1912번 - 연속합 (Java 8)

 

특정 값을 제거할때를 구하기 위해 연속합을 구하고, 반대방향으로도 연속합을 구한다.

 

제거할 값의 위치 전까지 연속합을 양쪽에서 구한다음 더해준다. 제거하지 않은 경우도 포함이므로, 연속합의 최댓값을 구할 때, 한 방향의 연속합도 포함시킨다.

 

참고 :

연속합의 최댓값을 구할 때, 첫 값을 안넣어서 계속 틀렸다. 원인을 못찾아서 아래 블로그에서 참고했다.

https://steady-coding.tistory.com/181