[백준] 연속합 2 (!) (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 연속합 2 (!) (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

 

첫번째 방법 ) DP를 1차원 배열로 2가지 구성

 

Left -> Right (index : 0 -> n-1) 방향으로 연속합 DP1 배열 을 구성

 

Right -> Left (index : n-1 -> 0) 방향으로 연속합 DP2 배열 을 구성

 

index : i 의 원소를 제외하는 경우의 연속합 최댓값을 갱신하며 구한다.

i 번째 원소를 제외한 연속합 = DP1[i-1] + DP2[i+1]

---

두번째 방법 ) DP를 2차원 배열로 구성

---

[JAVA 코드 - 첫번째 방법]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열 A의 크기 N (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

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

        // Left -> Right 방향 연속합
        int[] DP1 = new int[N];
        DP1[0] = arr[0];

        int max = DP1[0];

        for(int i=1; i<N; i++){
            DP1[i] = Math.max(DP1[i-1] + arr[i], arr[i]);

            // 아무런 값도 지우지 않은 경우 최댓값 구하기
            max = DP1[i] > max ? DP1[i] : max;
        }

        // Right -> Left 방향 연속합
        int[] DP2 = new int[N];
        DP2[N-1] = arr[N-1];
        for(int i=N-2; i>=0; i--){
            DP2[i] = Math.max(DP2[i+1] + arr[i], arr[i]);
        }

        // 특정 값을 지웠을 경우 + 아무런 값도 지우지 않았을 경우를 모두 포함하여 최댓값 구하기
        for(int i = 1; i<N-1; i++){
            // index : i 의 원소를 제거한 경우 최대 연속합
            int temp = DP1[i-1] + DP2[i+1];

            max = temp > max ? temp : max;
        }

        bw.write(max + "\n");        
        bw.flush();
        bw.close();
    }
}

 

---

[JAVA 코드 - 두번째 방법]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열 A의 크기 N (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

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

        int[][] DP = new int[N][2];
        DP[0][0] = DP[0][1] = arr[0];
        int max = DP[0][0];

        for(int i=1; i<N; i++){
            DP[i][0] = Math.max(DP[i-1][0] + arr[i], arr[i]);
            // DP[i-1][0]을 가져오는 경우 : 현재 수인 index : i 의 수를 지움
            // DP[i-1][1] + arr[i]를 가져오는 경우 : 이전에 수를 지운 경우가 있음 
            DP[i][1] = Math.max(DP[i-1][0], DP[i-1][1] + arr[i]);

            max = Math.max( max, Math.max(DP[i][0], DP[i][1]) );
        }
        
        bw.write(max + "\n");
        bw.flush();
        bw.close();
    }
}