연속합 2

📍 문제 설명

💡 접근

수를 제거하지 않는 최대합과 수를 한 번 제거하는 최대합을 표현하는 2차월 배열을 이용한다.

1. 수를 제거하지 않는 경우

이 경우에는 기존 연속합 문제와 동일하다.

2. 수를 제거하는 경우

이 경우에는 수를 제거 한 적이 있는지/없는지 판단하여 최댓값을 구한다.

수를 제거 한 적이 있으면 현재 인덱스의 숫자를 지우지 못하므로 dp[i-1][1] + arr[i]

수를 제거 한 적이 없으면 현재 인덱스의 숫자를 지울 수 있으므로 dp[i-1][0]

이 중의 최댓값이 dp[i][1]에 들어간다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static int[] arr;
    static int[][] dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = kb.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        //dp[i][0] 는 i번째 인덱스에서 수를 제거하지 않는 경우의 최댓값
        //dp[i][1] 는 i번째 인덱스에서 수를 한 번 제거하는 경우의 최댓값
        dp = new int[n][2];
        dp[0][0] = dp[0][1] = arr[0];
        //n = 1인 경우를 위해서
        answer = arr[0];

        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0] + arr[i], arr[i]);
            
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + arr[i]);

            answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
        }



    }

    private void solution() {
    }

}